Minimum Edge Dominating Sets
From MaRDI portal
Publication:3136610
DOI10.1137/0406030zbMath0782.05083OpenAlexW2083165612MaRDI QIDQ3136610
Publication date: 14 October 1993
Published in: SIAM Journal on Discrete Mathematics (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1137/0406030
Extremal problems in graph theory (05C35) Graph theory (including graph drawing) in computer science (68R10) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70) Graph theory (05C99)
Related Items (57)
Improved Budgeted Connected Domination and Budgeted Edge-Vertex Domination ⋮ Approximation hardness of edge dominating set problems ⋮ A natural family of optimization problems with arbitrarily small approximation thresholds ⋮ On the algorithmic complexity of edge total domination ⋮ Minimum maximal matchings in cubic graphs ⋮ The Complexity of Computing the Random Priority Allocation Matrix ⋮ Complementary nil vertex edge dominating sets ⋮ Maximal matching and edge domination in complete multipartite graphs ⋮ Hardness and approximation of minimum maximal matchings ⋮ Using maximality and minimality conditions to construct inequality chains ⋮ Modelling and solving the perfect edge domination problem ⋮ New Results on Directed Edge Dominating Set ⋮ On well-edge-dominated graphs ⋮ Minimum Maximal Matching Is NP-Hard in Regular Bipartite Graphs ⋮ Smallest maximal matchings of graphs ⋮ Hardness and approximation results for some variants of stable marriage problem ⋮ Incidence‐free sets and edge domination in incidence graphs ⋮ On the complexity of variations of mixed domination on graphs† ⋮ Domination versus edge domination ⋮ Complexity of finding graph roots with girth conditions ⋮ Approximation algorithms for clique-transversal sets and clique-independent sets in cubic graphs ⋮ An approximation algorithm dependent on edge-coloring number for minimum maximal matching problem ⋮ Algorithms and hardness results for edge total domination problem in graphs ⋮ On the \(d\)-claw vertex deletion problem ⋮ Parameterized algorithms for stable matching with ties and incomplete lists ⋮ On the semitotal domination number of line graphs ⋮ Approximability results for stable marriage problems with ties. ⋮ Improved budgeted connected domination and budgeted edge-vertex domination ⋮ Bounding and approximating minimum maximal matchings in regular graphs ⋮ Approximation algorithms for partially covering with edges ⋮ Algorithmic aspects of clique-transversal and clique-independent sets ⋮ Approximability of the capacitated \(b\)-edge dominating set problem ⋮ Approximating Dominating Set on Intersection Graphs of Rectangles and L-frames ⋮ Edge domination on bipartite permutation graphs and cotriangulated graphs ⋮ Generalizing the induced matching by edge capacity constraints ⋮ Integer programming formulations for the minimum weighted maximal matching problem ⋮ Linear time algorithms for generalized edge dominating set problems ⋮ The complexity of total edge domination and some related results on trees ⋮ Complexity and characterization aspects of edge-related domination for graphs ⋮ Aspects of upper defensive alliances ⋮ A $(2 - c \frac{\log {n}}{n})$ Approximation Algorithm for the Minimum Maximal Matching Problem ⋮ Algorithmic aspects of upper edge domination ⋮ On the \(d\)-claw vertex deletion problem ⋮ Fast and Simple Local Algorithms for 2-Edge Dominating Sets and 3-Total Vertex Covers ⋮ The stable marriage problem with master preference lists ⋮ Improved approximation bounds for edge dominating set in dense graphs ⋮ Decomposition algorithms for solving the minimum weight maximal matching problem ⋮ Maximal matching polytope in trees ⋮ Approximation Algorithms for Facial Cycles in Planar Embeddings ⋮ Approximating edge dominating set in dense graphs ⋮ On the algorithmic complexity of twelve covering and independence parameters of graphs ⋮ Small maximal matchings of random cubic graphs ⋮ On \(b\)-matchings and \(b\)-edge dominating sets: a 2-approximation algorithm for the 4-edge dominating set problem ⋮ Approximating dominating set on intersection graphs of rectangles and \(\mathsf{L}\)-frames ⋮ A note on approximations of directed edge dominating set ⋮ A 2-approximation algorithm for the minimum weight edge dominating set problem ⋮ Hard variants of stable marriage.
This page was built for publication: Minimum Edge Dominating Sets
