Minimum-cost \(b\)-edge dominating sets on trees
type: Item
instance of: scholarly article
title: Minimum-cost \(b\)-edge dominating sets on trees
zbMATH Open document ID: 1410.68168
author: Takehiro Ito
author: Naonori Kakimura
author: Naoyuki Kamiyama
author: Yusuke Kobayashi
author: Yoshio Okamoto
published in: Algorithmica
publication date: 2019-01-11T00:00:00Z
Mathematics Subject Classification ID: 68Q25
Mathematics Subject Classification ID: 05C69
Mathematics Subject Classification ID: 68W25
zbMATH DE Number: 7000189
zbMATH Keywords: edge dominating set
zbMATH Keywords: tree
zbMATH Keywords: dynamic programming
MaRDI profile type: Publication
full work available at URL: s00453-018-0448-z
OpenAlex ID: W2801071928
cites work: Approximability of the capacitated \(b\)-edge dominating set problem
cites work: Linear time algorithms for generalized edge dominating set problems
cites work: Erratum to: ``Linear time algorithms for generalized edge dominating set problems''
cites work: Enumerative Lattice Algorithms in any Norm Via M-ellipsoid Coverings
cites work: Deterministic Construction of an Approximate M-Ellipsoid and its Application to Derandomizing Lattice Algorithms
cites work: On Matchings and b-Edge Dominating Sets: A 2-Approximation Algorithm for the 3-Edge Dominating Set Problem
cites work: A 2-approximation algorithm for the minimum weight edge dominating set problem
cites work: Q4821303
cites work: Integer Programming with a Fixed Number of Variables
cites work: Q4828945
cites work: Q3818127
cites work: A Strongly Polynomial Algorithm to Solve Combinatorial Linear Programs
cites work: Q4782696
cites work: Edge Dominating Sets in Graphs
DOI: 10.1007/S00453-018-0448-Z
Recommended article: Minimum-Cost $$b$$-Edge Dominating Sets on Trees
Recommended article: On the number of minimum dominating sets in trees
Recommended article: Q6054234
Recommended article: Minimum Dominating Set Approximation in Graphs of Bounded Arboricity
Recommended article: Q3097133
Recommended article: The minimum dominating tree problem for graphs
Recommended article: Q6083402
Recommended article: Minimal 2-dominating sets in trees
Recommended article: Minimal dominating sets in interval graphs and trees
Recommended article: An exact solution framework for the minimum cost dominating tree problem
description: scientific article; zbMATH DE number 7000189