Approximating edge dominating set in dense graphs
From MaRDI portal
Recommendations
Cites work
- scientific article; zbMATH DE number 3639144 (Why is no real title available?)
- scientific article; zbMATH DE number 1163714 (Why is no real title available?)
- A $(2 - c \frac{\log {n}}{n})$ Approximation Algorithm for the Minimum Maximal Matching Problem
- A 2-approximation algorithm for the minimum weight edge dominating set problem
- A \(2\frac{1}{10}\)-approximation algorithm for a generalization of the weighted edge-dominating set problem
- Algorithm Theory - SWAT 2004
- An $n^{5/2} $ Algorithm for Maximum Matchings in Bipartite Graphs
- Approximating subdense instances of covering problems
- Approximating the dense set-cover problem
- Approximating vertex cover on dense graphs
- Approximation hardness of edge dominating set problems
- Computing and Combinatorics
- Connected vertex covers in dense graphs
- Edge Dominating Sets in Graphs
- Fast Algorithms for Maximum Subset Matching and All-Pairs Shortest Paths in Graphs with a (Not So) Small Vertex Cover
- Faster scaling algorithms for general graph matching problems
- Improved approximation bounds for edge dominating set in dense graphs
- Improved non-approximability results for minimum vertex cover with density constraints
- Minimum Edge Dominating Sets
- Minimum Maximal Matching Is NP-Hard in Regular Bipartite Graphs
- On the power of unique 2-prover 1-round games
- Polynomial time approximation schemes for some dense instances of NP-hard optimization problems
- Vertex cover might be hard to approximate to within \(2 - \varepsilon \)
- Vertex packings: Structural properties and algorithms
Cited in
(22)- A note on approximations of directed edge dominating set
- On approximating (connected) 2-edge dominating set by a tree
- Bounding and approximating minimum maximal matchings in regular graphs
- On approximating (connected) 2-edge dominating set by a tree
- Algorithmic aspects of upper edge domination
- On \(b\)-matchings and \(b\)-edge dominating sets: a 2-approximation algorithm for the 4-edge dominating set problem
- Hardness and approximation of minimum maximal matchings
- Approximating edge dominating set in dense graphs
- scientific article; zbMATH DE number 1670532 (Why is no real title available?)
- Fast and simple local algorithms for 2-edge dominating sets and 3-total vertex covers
- Improved approximation bounds for edge dominating set in dense graphs
- Domination versus edge domination
- Tight inapproximability of minimum maximal matching on bipartite graphs and related problems
- scientific article; zbMATH DE number 2080196 (Why is no real title available?)
- Decomposition algorithms for solving the minimum weight maximal matching problem
- Edge domination number and the number of minimum edge dominating sets in pseudofractal scale-free web and Sierpiński gasket
- Approximation hardness of edge dominating set problems
- Minimum maximal matchings in cubic graphs
- On kernelization for edge dominating set under structural parameters
- New results on polynomial inapproximability and fixed parameter approximability of Edge Dominating Set
- New results on directed edge dominating set
- Improved Approximation Bounds for Edge Dominating Set in Dense Graphs
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)
