Minimum-Cost $$b$$-Edge Dominating Sets on Trees

DOI10.1007/978-3-319-13075-0_16zbMath1432.68181OpenAlexW2263731576MaRDI QIDQ2942628

Yoshio Okamoto, Takehiro Ito, Yusuke Kobayashi, Naoyuki Kamiyama, Naonori Kakimura

Publication date: 11 September 2015

Published in: Algorithms and Computation (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/978-3-319-13075-0_16

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Nonnumerical algorithms (68W05) Graph algorithms (graph-theoretic aspects) (05C85) Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) (05C69) Approximation algorithms (68W25)

Related Items (1)

On the star forest polytope for trees and cycles

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• A 2-approximation algorithm for the minimum weight edge dominating set problem
• Erratum to: ``Linear time algorithms for generalized edge dominating set problems
• Approximability of the capacitated \(b\)-edge dominating set problem
• Linear time algorithms for generalized edge dominating set problems
• A Strongly Polynomial Algorithm to Solve Combinatorial Linear Programs
• Integer Programming with a Fixed Number of Variables
• Edge Dominating Sets in Graphs
• Enumerative Lattice Algorithms in any Norm Via M-ellipsoid Coverings
• Deterministic Construction of an Approximate M-Ellipsoid and its Application to Derandomizing Lattice Algorithms

This page was built for publication: Minimum-Cost $$b$$-Edge Dominating Sets on Trees