Algorithms for the minimum weight \(k\)-fold (connected) dominating set problem

DOI10.1007/s10878-010-9372-0zbMath1244.90234OpenAlexW2036620201MaRDI QIDQ437058

Wenkai Ma, Zhao Zhang, Deying Li

Publication date: 17 July 2012

Published in: Journal of Combinatorial Optimization (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/s10878-010-9372-0

zbMATH Keywords

algorithm\(k\)-fold dominating setslab decompositionunit ball graph

Mathematics Subject Classification ID

Programming involving graphs or networks (90C35) Combinatorial optimization (90C27)

Related Items (1)

Approximation for minimum strongly connected dominating and absorbing set with routing-cost constraint in disk digraphs

Cites Work

• Unnamed Item
• Unnamed Item
• A greedy approximation for minimum connected dominating sets
• A PTAS for minimum connected dominating set in 3-dimensional wireless sensor networks
• Unit disk graphs
• Approximation algorithms for combinatorial problems
• Approximation algorithms for connected dominating sets
• Improving construction for connected dominating set with Steiner tree in wireless sensor networks
• A threshold of ln n for approximating set cover
• NC-Approximation Schemes for NP- and PSPACE-Hard Problems for Geometric Graphs
• A polynomial-time approximation scheme for the minimum-connected dominating set in ad hoc wireless networks
• Graph-Theoretic Concepts in Computer Science
• Constant-time distributed dominating set approximation

This page was built for publication: Algorithms for the minimum weight \(k\)-fold (connected) dominating set problem