Approximating edge dominating set in dense graphs
From MaRDI portal
Publication:764308
DOI10.1016/j.tcs.2011.10.001zbMath1235.68079OpenAlexW2173985621MaRDI QIDQ764308
Claus Viehmann, Richard Schmied
Publication date: 13 March 2012
Published in: Theoretical Computer Science (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1016/j.tcs.2011.10.001
approximation algorithmsdense instancesedge dominating setapproximation lower boundsminimum maximal matching
Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Graph algorithms (graph-theoretic aspects) (05C85) Approximation algorithms (68W25)
Related Items
On approximating (connected) 2-edge dominating set by a tree ⋮ Minimum maximal matchings in cubic graphs ⋮ Hardness and approximation of minimum maximal matchings ⋮ New Results on Directed Edge Dominating Set ⋮ Domination versus edge domination ⋮ Bounding and approximating minimum maximal matchings in regular graphs ⋮ On Approximating (Connected) 2-Edge Dominating Set by a Tree ⋮ Unnamed Item ⋮ Algorithmic aspects of upper edge domination ⋮ Fast and Simple Local Algorithms for 2-Edge Dominating Sets and 3-Total Vertex Covers ⋮ Decomposition algorithms for solving the minimum weight maximal matching problem ⋮ Tight inapproximability of minimum maximal matching on bipartite graphs and related problems ⋮ On \(b\)-matchings and \(b\)-edge dominating sets: a 2-approximation algorithm for the 4-edge dominating set problem ⋮ A note on approximations of directed edge dominating set ⋮ New results on polynomial inapproximability and fixed parameter approximability of Edge Dominating Set ⋮ EDGE DOMINATION NUMBER AND THE NUMBER OF MINIMUM EDGE DOMINATING SETS IN PSEUDOFRACTAL SCALE-FREE WEB AND SIERPIŃSKI GASKET
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Connected vertex covers in dense graphs
- Improved approximation bounds for edge dominating set in dense graphs
- A 2-approximation algorithm for the minimum weight edge dominating set problem
- Approximating the dense set-cover problem
- Improved non-approximability results for minimum vertex cover with density constraints
- Approximation hardness of edge dominating set problems
- Vertex cover might be hard to approximate to within \(2 - \varepsilon \)
- Approximating Subdense Instances of Covering Problems
- Minimum Edge Dominating Sets
- Minimum Maximal Matching Is NP-Hard in Regular Bipartite Graphs
- Fast Algorithms for Maximum Subset Matching and All-Pairs Shortest Paths in Graphs with a (Not So) Small Vertex Cover
- On the power of unique 2-prover 1-round games
- A $(2 - c \frac{\log {n}}{n})$ Approximation Algorithm for the Minimum Maximal Matching Problem
- Edge Dominating Sets in Graphs
- Vertex packings: Structural properties and algorithms
- Faster scaling algorithms for general graph matching problems
- Algorithm Theory - SWAT 2004
- An $n^{5/2} $ Algorithm for Maximum Matchings in Bipartite Graphs
- Computing and Combinatorics
- Polynomial time approximation schemes for some dense instances of NP-hard optimization problems
- A \(2\frac{1}{10}\)-approximation algorithm for a generalization of the weighted edge-dominating set problem
