Approximability of the capacitated b-edge dominating set problem

DOI10.1016/J.TCS.2007.06.009MaRDI QIDQ2456372zbMATH OpenOpenAlexFDO

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

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 algorithmedge dominating setintegrality gap

Mathematics Subject Classification ID

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

Recommendations

• Computing and Combinatorics
• New results on polynomial inapproximability and fixed parameter approximability of \textsc{Edge Dominating Set}
• New results on polynomial inapproximability and fixed parameter approximability of Edge Dominating Set
• Approximation hardness of edge dominating set problems
• On approximability of the independent/connected edge dominating set problems

Cites work

• A 1-matching blossom-type algorithm for edge covering problems
• 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
• Algorithms and Computation
• Algorithms and Data Structures
• Approximating the tree and tour covers of a graph
• Approximation algorithms for metric facility location and k -Median problems using the primal-dual schema and Lagrangian relaxation
• Combinatorial optimization. Polyhedra and efficiency (3 volumes)
• Edge Dominating Sets in Graphs
• Edge domination on bipartite permutation graphs and cotriangulated graphs
• scientific article; zbMATH DE number 3674114 (Why is no real title available?)
• scientific article; zbMATH DE number 2119674 (Why is no real title available?)
• Improved approximations for tour and tree covers
• Minimum Edge Dominating Sets

Cited in

(15)

• Improved approximation bounds for edge dominating set in dense graphs
• On approximating (connected) 2-edge dominating set by a tree
• Minimum-cost b-edge dominating sets on trees
• Integer programming formulations for the minimum weighted maximal matching problem
• On \(b\)-matchings and \(b\)-edge dominating sets: a 2-approximation algorithm for the 4-edge dominating set problem
• Generalizing the induced matching by edge capacity constraints
• Linear time algorithms for generalized edge dominating set problems
• Fast and simple local algorithms for 2-edge dominating sets and 3-total vertex covers
• Decomposition algorithms for solving the minimum weight maximal matching problem
• Minimum-cost \(b\)-edge dominating sets on trees
• Near Linear Time Approximation Schemes for Uncapacitated and Capacitated b–Matching Problems in Nonbipartite Graphs
• Computing and Combinatorics
• On approximating (connected) 2-edge dominating set by a tree
• Extension of some edge graph problems: standard, parameterized and approximation complexity
• Approximation algorithms for partially covering with edges

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

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