Improved approximation bounds for edge dominating set in dense graphs

DOI10.1016/j.tcs.2008.12.036zbMath1165.68055MaRDI QIDQ1006077

Stefan Langerman, Jean Cardinal, Eythan Levy

Publication date: 17 March 2009

Published in: Theoretical Computer Science (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.tcs.2008.12.036

zbMATH Keywords

approximation algorithm; greedy algorithm; edge dominating set; minimum maximal matching; dense graph

Mathematics Subject Classification ID

68R10: Graph theory (including graph drawing) in computer science

68W25: Approximation algorithms

Uses Software

• GraPHedron

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Facet defining inequalities among graph invariants: The system graphedron
• A 2-approximation algorithm for the minimum weight edge dominating set problem
• Approximation hardness of edge dominating set problems
• Approximability of the capacitated \(b\)-edge dominating set problem
• Linear time algorithms for generalized edge dominating set problems
• Minimum Edge Dominating Sets
• Improved Approximation Algorithms for the Vertex Cover Problem in Graphs and Hypergraphs
• edge dominating set: Efficient Enumeration-Based Exact Algorithms
• Minimum Maximal Matching Is NP-Hard in Regular Bipartite Graphs
• Exact Algorithms for Edge Domination
• Edge Dominating Sets in Graphs
• Branching and Treewidth Based Exact Algorithms
• Computing and Combinatorics
• A \(2\frac{1}{10}\)-approximation algorithm for a generalization of the weighted edge-dominating set problem