Minimum-cost \(b\)-edge dominating sets on trees

DOI10.1007/s00453-018-0448-zzbMath1410.68168OpenAlexW2801071928MaRDI QIDQ1755793

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

Publication date: 11 January 2019

Published in: Algorithmica (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/s00453-018-0448-z

zbMATH Keywords

treedynamic programmingedge dominating set

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) (05C69) Approximation algorithms (68W25)

Related Items (2)

On \(b\)-matchings and \(b\)-edge dominating sets: a 2-approximation algorithm for the 4-edge dominating set problem ⋮ EDGE DOMINATION NUMBER AND THE NUMBER OF MINIMUM EDGE DOMINATING SETS IN PSEUDOFRACTAL SCALE-FREE WEB AND SIERPIŃSKI GASKET

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
• On Matchings and b-Edge Dominating Sets: A 2-Approximation Algorithm for the 3-Edge Dominating Set Problem
• 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