Improved approximation bounds for edge dominating set in dense graphs

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

Jean Cardinal, Stefan Langerman, 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 algorithmgreedy algorithmedge dominating setminimum maximal matchingdense graph

Mathematics Subject Classification ID

Graph theory (including graph drawing) in computer science (68R10) Approximation algorithms (68W25)

Related Items

Minimum maximal matchings in cubic graphs, Hardness and approximation of minimum maximal matchings, New Results on Directed Edge Dominating Set, New parameterized algorithms for the edge dominating set problem, Improved approximation for spanning star forest in dense graphs, On the \(k\)-edge-incident subgraph problem and its variants, Bounding and approximating minimum maximal matchings in regular graphs, Approximating Edge Dominating Set in Dense Graphs, Integer programming formulations for the minimum weighted maximal matching problem, Unnamed Item, Maximal matching polytope in trees, Approximating edge dominating set in dense graphs, 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

Uses Software

• GraPHedron

Cites Work

• 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
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item