EFFICIENT DISTRIBUTED ALGORITHMS FOR TOPOLOGY CONTROL PROBLEM WITH SHORTEST PATH CONSTRAINTS

DOI10.1142/S1793830909000348zbMath1184.68364OpenAlexW2147926631MaRDI QIDQ5189986

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

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)

Related Items (7)

Approximation for minimum strongly connected dominating and absorbing set with routing-cost constraint in disk digraphs ⋮ On the union of intermediate nodes of shortest paths ⋮ Polynomial-time approximation scheme for minimum connected dominating set under routing cost constraint in wireless sensor networks ⋮ Wireless networking, dominating and packing ⋮ On minimum submodular cover with submodular cost ⋮ A PTAS for Weak Minimum Routing Cost Connected Dominating Set of Unit Disk Graph ⋮ PTAS for routing-cost constrained minimum connected dominating set in growth bounded graphs

Cites Work

• Unit disk graphs
• Simple distributed \(\Delta+1\)-coloring of graphs
• Improving construction for connected dominating set with Steiner tree in wireless sensor networks
• Planar Formulae and Their Uses
• On the hardness of approximating minimization problems
• 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
• Simple heuristics for unit disk graphs

This page was built for publication: EFFICIENT DISTRIBUTED ALGORITHMS FOR TOPOLOGY CONTROL PROBLEM WITH SHORTEST PATH CONSTRAINTS