Approximating edge dominating set in dense graphs
DOI10.1016/J.TCS.2011.10.001zbMATH Open1235.68079OpenAlexW2173985621MaRDI QIDQ764308FDOQ764308
Authors: Richard Schmied, Claus Viehmann 
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
Recommendations
approximation algorithmsedge dominating setdense instancesapproximation lower boundsminimum maximal matching
Graph algorithms (graph-theoretic aspects) (05C85) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Approximation algorithms (68W25)
Cites Work
- Title not available (Why is that?)
- Vertex cover might be hard to approximate to within \(2 - \varepsilon \)
- Faster scaling algorithms for general graph matching problems
- An $n^{5/2} $ Algorithm for Maximum Matchings in Bipartite Graphs
- Vertex packings: Structural properties and algorithms
- On the power of unique 2-prover 1-round games
- Edge Dominating Sets in Graphs
- Minimum Edge Dominating Sets
- Approximating vertex cover on 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 subdense instances of covering problems
- Title not available (Why is that?)
- Connected vertex covers in dense graphs
- Approximating the dense set-cover problem
- Improved non-approximability results for minimum vertex cover with density constraints
- Polynomial time approximation schemes for some dense instances of NP-hard optimization problems
- Fast Algorithms for Maximum Subset Matching and All-Pairs Shortest Paths in Graphs with a (Not So) Small Vertex Cover
- A \(2\frac{1}{10}\)-approximation algorithm for a generalization of the weighted edge-dominating set problem
- Computing and Combinatorics
- Approximation hardness of edge dominating set problems
- Minimum Maximal Matching Is NP-Hard in Regular Bipartite Graphs
- A $(2 - c \frac{\log {n}}{n})$ Approximation Algorithm for the Minimum Maximal Matching Problem
- Algorithm Theory - SWAT 2004
Cited In (22)
- Title not available (Why is that?)
- Improved approximation bounds for edge dominating set in dense graphs
- Minimum maximal matchings in cubic graphs
- Hardness and approximation of minimum maximal matchings
- Fast and simple local algorithms for 2-edge dominating sets and 3-total vertex covers
- Tight inapproximability of minimum maximal matching on bipartite graphs and related problems
- On approximating (connected) 2-edge dominating set by a tree
- On approximating (connected) 2-edge dominating set by a tree
- Bounding and approximating minimum maximal matchings in regular graphs
- Title not available (Why is that?)
- Algorithmic aspects of upper edge domination
- New results on polynomial inapproximability and fixed parameter approximability of Edge Dominating Set
- Decomposition algorithms for solving the minimum weight maximal matching problem
- Approximating edge dominating set in dense graphs
- Improved Approximation Bounds for Edge Dominating Set in Dense Graphs
- Domination versus edge domination
- On \(b\)-matchings and \(b\)-edge dominating sets: a 2-approximation algorithm for the 4-edge dominating set problem
- New results on directed edge dominating set
- Title not available (Why is that?)
- Edge domination number and the number of minimum edge dominating sets in pseudofractal scale-free web and Sierpiński gasket
- A note on approximations of directed edge dominating set
- Approximation hardness of edge dominating set problems
This page was built for publication: Approximating edge dominating set in dense graphs
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q764308)
