Algorithms for minimum connected capacitated dominating set problem

DOI10.1142/S1793830911000961MaRDI QIDQ3007757zbMATH OpenOpenAlexFDO

Authors Xiumei Wang, Weiping Shang

Publication date 17 June 2011

Published in Discrete Mathematics, Algorithms and Applications (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1142/s1793830911000961

zbMATH Keywords

approximation algorithmcapacitated dominating setunit disk graph

Mathematics Subject Classification ID

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

Recommendations

• Algorithms for Minimum m-Connected k-Dominating Set Problem
• Algorithms for minimum \(m\)-connected \(k\)-tuple dominating set problem
• A distributed approximation algorithm for the bottleneck connected dominating set problem
• Efficient algorithm for finding minimum connected dominating set in wireless sensor networks
• Approximation algorithms for connected dominating sets

Cites work

• Generalized submodular cover problems and applications
• How to Allocate Network Centers
• Minimum connected dominating sets and maximal independent sets in unit disk graphs

Cited in

(8)

• A distributed approximation algorithm for the bottleneck connected dominating set problem
• Improving construction for connected dominating set with Steiner tree in wireless sensor networks
• Efficient algorithm for finding minimum connected dominating set in wireless sensor networks
• Algorithms for Minimum m-Connected k-Dominating Set Problem
• Connected dominating set. Theory and applications
• Algorithms for the minimum weight k-fold (connected) dominating set problem
• An efficient algorithm for constructing a connected dominating set in mobile ad hoc networks
• An efficient connected dominating set algorithm in WSNS based on the induced tree of the crossed cube

This page was built for publication: Algorithms for minimum connected capacitated dominating set problem

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