A greedy approximation for minimum connected dominating sets

DOI10.1016/J.TCS.2004.08.013MaRDI QIDQ706637zbMATH OpenOpenAlexWikidataFDO

Authors Lu Ruan, Weili Wu, Yingshu Li, Hongwei Du, X.-H. Jia, Ker-I Ko

Publication date 9 February 2005

Published in Theoretical Computer Science (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/j.tcs.2004.08.013

zbMATH Keywords

Connected dominating setgreedy approximation

Mathematics Subject Classification ID

Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) (05C69) Graph theory (including graph drawing) in computer science (68R10) Approximation algorithms (68W25)

Recommendations

• A unified greedy approximation for several dominating set problems
• Minimum connected dominating sets in finite graphs
• Approximation algorithms for connected dominating sets
• A polynomial-time approximation scheme for the minimum-connected dominating set in ad hoc wireless networks
• Approximation algorithms for connected dominating sets

Cites work

• `` Strong NP-Completeness Results
• A polynomial-time approximation scheme for the minimum-connected dominating set in ad hoc wireless networks
• Approximation algorithms for connected dominating sets
• Maximizing Submodular Set Functions: Formulations and Analysis of Algorithms

This page was built for publication: A greedy approximation for minimum connected dominating sets

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