Improved Approximation Bounds for Edge Dominating Set in Dense Graphs

DOI10.1007/11970125_9zbMath1129.90363OpenAlexW2175923664MaRDI QIDQ5443513

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

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

Related Items (4)

Connected Vertex Covers in Dense Graphs ⋮ Facet defining inequalities among graph invariants: The system graphedron ⋮ Connected vertex covers in dense graphs ⋮ A $(2 - c \frac{\log {n}}{n})$ Approximation Algorithm for the Minimum Maximal Matching Problem

This page was built for publication: Improved Approximation Bounds for Edge Dominating Set in Dense Graphs