Approximability of the capacitated \(b\)-edge dominating set problem

DOI10.1016/j.tcs.2007.06.009zbMath1124.68115OpenAlexW2101439434MaRDI QIDQ2456372

Takuro Fukunaga, Ojas Parekh, Hiroshi Nagamochi, André Berger

Publication date: 18 October 2007

Published in: Theoretical Computer Science (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.tcs.2007.06.009

zbMATH Keywords

approximation algorithmintegrality gapedge dominating set

Mathematics Subject Classification ID

Graph theory (including graph drawing) in computer science (68R10) Approximation algorithms (68W25)

Related Items (14)

On approximating (connected) 2-edge dominating set by a tree ⋮ Minimum-Cost $$b$$-Edge Dominating Sets on Trees ⋮ Extension of some edge graph problems: standard, parameterized and approximation complexity ⋮ Approximation algorithms for partially covering with edges ⋮ Generalizing the induced matching by edge capacity constraints ⋮ Covering problems in edge- and node-weighted graphs ⋮ Minimum-cost \(b\)-edge dominating sets on trees ⋮ Integer programming formulations for the minimum weighted maximal matching problem ⋮ Linear time algorithms for generalized edge dominating set problems ⋮ On Approximating (Connected) 2-Edge Dominating Set by a Tree ⋮ Fast and Simple Local Algorithms for 2-Edge Dominating Sets and 3-Total Vertex Covers ⋮ Improved approximation bounds for edge dominating set in dense graphs ⋮ Decomposition algorithms for solving the minimum weight maximal matching problem ⋮ On \(b\)-matchings and \(b\)-edge dominating sets: a 2-approximation algorithm for the 4-edge dominating set problem

Cites Work

• Unnamed Item
• Unnamed Item
• Edge domination on bipartite permutation graphs and cotriangulated graphs
• Approximating the tree and tour covers of a graph
• A 2-approximation algorithm for the minimum weight edge dominating set problem
• Combinatorial optimization. Polyhedra and efficiency (3 volumes)
• Improved approximations for tour and tree covers
• Minimum Edge Dominating Sets
• Approximation algorithms for metric facility location and k -Median problems using the primal-dual schema and Lagrangian relaxation
• Edge Dominating Sets in Graphs
• A 1-matching blossom-type algorithm for edge covering problems
• Algorithms and Computation
• Algorithms and Data Structures
• A \(2\frac{1}{10}\)-approximation algorithm for a generalization of the weighted edge-dominating set problem

This page was built for publication: Approximability of the capacitated \(b\)-edge dominating set problem