Linear time algorithms for generalized edge dominating set problems

DOI10.1007/S00453-007-9057-YMaRDI QIDQ2480902zbMATH OpenOpenAlexFDO

Authors André Berger, Ojas Parekh

Publication date 3 April 2008

Published in Algorithmica (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/s00453-007-9057-y

zbMATH Keywords

treesapproximation algorithmedge dominating set

Mathematics Subject Classification ID

Graph algorithms (graph-theoretic aspects) (05C85) Approximation algorithms (68W25) Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) (05C69)

Recommendations

• Algorithms and Data Structures
• A 2-approximation algorithm for the minimum weight edge dominating set problem
• scientific article; zbMATH DE number 1670653
• An improved algorithm for parameterized edge dominating set problem
• scientific article; zbMATH DE number 2119674

Cites work

• scientific article; zbMATH DE number 434499 (Why is no real title available?)
• scientific article; zbMATH DE number 3121293 (Why is no real title available?)
• scientific article; zbMATH DE number 3674114 (Why is no real title available?)
• scientific article; zbMATH DE number 1304326 (Why is no real title available?)
• scientific article; zbMATH DE number 1839431 (Why is no real title available?)
• scientific article; zbMATH DE number 2119674 (Why is no real title available?)
• scientific article; zbMATH DE number 3290993 (Why is no real title available?)
• scientific article; zbMATH DE number 3185974 (Why is no real title available?)
• A 2-approximation algorithm for the minimum weight edge dominating set problem
• A \(2\frac{1}{10}\)-approximation algorithm for a generalization of the weighted edge-dominating set problem
• Approximability of the capacitated \(b\)-edge dominating set problem
• Combinatorial optimization. Polyhedra and efficiency (3 volumes)
• Edge Dominating Sets in Graphs
• Edge domination on bipartite permutation graphs and cotriangulated graphs
• Minimum Edge Dominating Sets
• On approximability of the independent/connected edge dominating set problems
• Optimization, approximation, and complexity classes
• The edge domination problem

Cited in

(15)

• Improved approximation bounds for edge dominating set in dense graphs
• Fast and simple local algorithms for 2-edge dominating sets and 3-total vertex covers
• The prize-collecting edge dominating set problem in trees
• Erratum to: ``Linear time algorithms for generalized edge dominating set problems
• New Parameterized Algorithms for the Edge Dominating Set Problem
• Minimum-cost b-edge dominating sets on trees
• Minimum-cost \(b\)-edge dominating sets on trees
• scientific article; zbMATH DE number 2119674 (Why is no real title available?)
• On well-edge-dominated graphs
• Algorithms and Data Structures
• Linear algorithms for edge-vertex domination in trees
• Some graph classes and the Wimer edge variant
• Extension of some edge graph problems: standard, parameterized and approximation complexity
• On total unimodularity of edge-edge adjacency matrices
• On \(b\)-matchings and \(b\)-edge dominating sets: a 2-approximation algorithm for the 4-edge dominating set problem

This page was built for publication: Linear time algorithms for generalized edge dominating set problems

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