Efficient distributed algorithms for topology control problem with shortest path constraints

DOI10.1142/S1793830909000348MaRDI QIDQ5189986zbMATH OpenOpenAlexFDO

Authors James Willson, Xiaofeng Gao, Zhonghua Qu, Yi Zhu, Yingshu Li, Weili Wu

Publication date 11 March 2010

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

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

zbMATH Keywords

shortest pathdistributed algorithmconnected dominating set

Mathematics Subject Classification ID

Graph theory (including graph drawing) in computer science (68R10) Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) (05C69) Approximations and expansions (41A99)

Recommendations

• A distributed approximation algorithm for the bottleneck connected dominating set problem
• An exact algorithm for minimum CDS with shortest path constraint in wireless networks
• Routing-efficient CDS construction in disk-containment graphs
• Algorithms for Minimum m-Connected k-Dominating Set Problem
• On the construction of \(k\)-connected \(m\)-dominating sets in wireless networks

Cites work

• A polynomial-time approximation scheme for the minimum-connected dominating set in ad hoc wireless networks
• Improving construction for connected dominating set with Steiner tree in wireless sensor networks
• NC-Approximation Schemes for NP- and PSPACE-Hard Problems for Geometric Graphs
• On the hardness of approximating minimization problems
• Planar Formulae and Their Uses
• Simple distributed \(\Delta+1\)-coloring of graphs
• Simple heuristics for unit disk graphs
• Unit disk graphs

Cited in

(12)

• Routing-efficient CDS construction in disk-containment graphs
• An exact algorithm for minimum CDS with shortest path constraint in wireless networks
• PTAS for routing-cost constrained minimum connected dominating set in growth bounded graphs
• Polynomial-time approximation scheme for minimum connected dominating set under routing cost constraint in wireless sensor networks
• On the union of intermediate nodes of shortest paths
• Distributed Computing – IWDC 2005
• Wireless networking, dominating and packing
• The optimal design of low-latency virtual backbones
• Approximation for minimum strongly connected dominating and absorbing set with routing-cost constraint in disk digraphs
• CONSTRAINED SHORTEST PATH ALGORITHMS FOR NETWORK CONTROL
• A PTAS for weak minimum routing cost connected dominating set of unit disk graph
• On minimum submodular cover with submodular cost

This page was built for publication: Efficient distributed algorithms for topology control problem with shortest path constraints

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