Approximating edge dominating set in dense graphs

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

zbMATH Keywords

approximation algorithmsdense instancesedge dominating setapproximation lower boundsminimum maximal matching

Mathematics Subject Classification ID

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