Approximating Edge Dominating Set in Dense Graphs
DOI10.1007/978-3-642-20877-5_5zbMath1330.68125OpenAlexW2133360442MaRDI QIDQ3010383
Claus Viehmann, Richard Schmied
Publication date: 1 July 2011
Published in: Lecture Notes in Computer Science (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1007/978-3-642-20877-5_5
approximation algorithmsdense instancesedge dominating setapproximation lower boundsminimum maximal matching
Analysis of algorithms and problem complexity (68Q25) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) (05C69) Approximation algorithms (68W25)
Cites Work
- Unnamed Item
- Unnamed Item
- Improved approximation bounds for edge dominating set in dense graphs
- 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
- Fast Algorithms for Maximum Subset Matching and All-Pairs Shortest Paths in Graphs with a (Not So) Small Vertex Cover
- 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
This page was built for publication: Approximating Edge Dominating Set in Dense Graphs
