A \(2\frac{1}{10}\)-approximation algorithm for a generalization of the weighted edge-dominating set problem
From MaRDI portal
Publication:5952320
DOI10.1023/A:1011445210568zbMath1078.90061MaRDI QIDQ5952320
Goran Konjevod, Robert D. Carr, Toshihiro Fujito, Ojas Parekh
Publication date: 2001
Published in: Journal of Combinatorial Optimization (Search for Journal in Brave)
Programming involving graphs or networks (90C35) Special problems of linear programming (transportation, multi-index, data envelopment analysis, etc.) (90C08) Graph algorithms (graph-theoretic aspects) (05C85) Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) (05C69)
Related Items (17)
Approximation hardness of edge dominating set problems ⋮ Approximating the Minimum Tour Cover with a Compact Linear Program ⋮ Exact Algorithms for Edge Domination ⋮ Approximation algorithms for \(k\)-hurdle problems ⋮ Domination versus edge domination ⋮ Exact algorithms for edge domination ⋮ Bounding and approximating minimum maximal matchings in regular graphs ⋮ Approximability of the capacitated \(b\)-edge dominating set problem ⋮ Generalizing the induced matching by edge capacity constraints ⋮ Covering problems in edge- and node-weighted graphs ⋮ Linear time algorithms for generalized edge dominating set problems ⋮ A $(2 - c \frac{\log {n}}{n})$ Approximation Algorithm for the Minimum Maximal Matching Problem ⋮ Improved approximation bounds for edge dominating set in dense graphs ⋮ Path hitting in acyclic graphs ⋮ Approximating edge dominating set in dense graphs ⋮ On \(b\)-matchings and \(b\)-edge dominating sets: a 2-approximation algorithm for the 4-edge dominating set problem ⋮ New results on polynomial inapproximability and fixed parameter approximability of Edge Dominating Set
This page was built for publication: A \(2\frac{1}{10}\)-approximation algorithm for a generalization of the weighted edge-dominating set problem
