A 2110-approximation algorithm for a generalization of the weighted edge-dominating set problem

DOI10.1023/A:1011445210568MaRDI QIDQ5952320zbMATH OpenFDO

Authors Robert D. Carr, Toshihiro Fujito, Goran Konjevod, Ojas Parekh

Publication date 2001

Published in Journal of Combinatorial Optimization (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1023/A:1011445210568

zbMATH Keywords

edge coververtex cover

Mathematics Subject Classification ID

Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) (05C69) Graph algorithms (graph-theoretic aspects) (05C85) Special problems of linear programming (transportation, multi-index, data envelopment analysis, etc.) (90C08) Programming involving graphs or networks (90C35)

Recommendations

• scientific article; zbMATH DE number 1670653
• Algorithms and Data Structures
• A 2-approximation algorithm for the minimum weight edge dominating set problem
• scientific article; zbMATH DE number 2119674
• On approximability of the independent/connected edge dominating set problems

Cited in

(20)

• Improved approximation bounds for edge dominating set in dense graphs
• Path hitting in acyclic graphs
• A 2-approximation algorithm for the minimum weight edge dominating set problem
• Exact algorithms for edge domination
• On \(b\)-matchings and \(b\)-edge dominating sets: a 2-approximation algorithm for the 4-edge dominating set problem
• Domination versus edge domination
• Bounding and approximating minimum maximal matchings in regular graphs
• New results on polynomial inapproximability and fixed parameter approximability of Edge Dominating Set
• Approximation hardness of edge dominating set problems
• Approximability of the capacitated \(b\)-edge dominating set problem
• Generalizing the induced matching by edge capacity constraints
• Linear time algorithms for generalized edge dominating set problems
• scientific article; zbMATH DE number 1670653 (Why is no real title available?)
• Approximating the Minimum Tour Cover with a Compact Linear Program
• Exact Algorithms for Edge Domination
• A $(2 - c \frac{\log {n}}{n})$ Approximation Algorithm for the Minimum Maximal Matching Problem
• scientific article; zbMATH DE number 2119674 (Why is no real title available?)
• Upper and lower bounds on approximating weighted mixed domination
• Approximation algorithms for \(k\)-hurdle problems
• Approximating edge dominating set in dense graphs

This page was built for publication: A \(2\frac{1}{10}\)-approximation algorithm for a generalization of the weighted edge-dominating set problem

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5952320)