Improved Approximation Bounds for Edge Dominating Set in Dense Graphs

DOI10.1007/11970125_9MaRDI QIDQ5443513zbMATH OpenOpenAlexFDO

Authors Jean Cardinal, Stefan Langerman, Eythan Levy

Publication date 21 February 2008

Published in Approximation and Online Algorithms (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/11970125_9

Mathematics Subject Classification ID

Approximation algorithms (68W25) Programming involving graphs or networks (90C35) Approximation methods and heuristics in mathematical programming (90C59)

Recommendations

• Improved approximation bounds for edge dominating set in dense graphs
• Approximating edge dominating set in dense graphs
• Approximating edge dominating set in dense graphs
• Approximation hardness of edge dominating set problems
• Algorithms and Computation

Cited in

(9)

• Improved approximation bounds for edge dominating set in dense graphs
• Approximating edge dominating set in dense graphs
• Connected Vertex Covers in Dense Graphs
• A $(2 - c \frac{\log {n}}{n})$ Approximation Algorithm for the Minimum Maximal Matching Problem
• Improved Budgeted Connected Domination and Budgeted Edge-Vertex Domination
• Distributed algorithms for \textsc{Edge Dominating Sets}
• Approximating edge dominating set in dense graphs
• Facet defining inequalities among graph invariants: The system graphedron
• Connected vertex covers in dense graphs

This page was built for publication: Improved Approximation Bounds for 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 Q5443513)