Local Algorithms for Dominating and Connected Dominating Sets of Unit Disk Graphs with Location Aware Nodes

DOI10.1007/978-3-540-78773-0_14zbMath1136.68453OpenAlexW25150355MaRDI QIDQ5458525

No author found.

Publication date: 15 April 2008

Published in: Lecture Notes in Computer Science (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/978-3-540-78773-0_14

zbMATH Keywords

Dominating setConnected dominating setLocation awarenessApproximation factorLocal algorithmUnit disk graph

Mathematics Subject Classification ID

Graph theory (including graph drawing) in computer science (68R10) Graph algorithms (graph-theoretic aspects) (05C85) Network protocols (68M12)

Related Items (6)

Impact of locality on location aware unit disk graphs ⋮ A self-stabilizing 6-approximation for the minimum connected dominating set with safe convergence in unit disk graphs ⋮ An asynchronous self-stabilizing approximation for the minimum CDS with safe convergence in UDGs ⋮ Analysing local algorithms in location-aware quasi-unit-disk graphs ⋮ Local PTAS for Dominating and Connected Dominating Set in Location Aware Unit Disk Graphs ⋮ Approximation and heuristic algorithms for computing backbones in asymmetric ad-hoc networks

Cites Work

• Unnamed Item
• On approximating the minimum independent dominating set
• Broadcasting in geometric radio networks
• Unit disk graphs
• Approximation algorithms for combinatorial problems
• Unit disk graph recognition is NP-hard
• Discrete mobile centers
• Local Construction of Planar Spanners in Unit Disk Graphs with Irregular Transmission Ranges
• The price of being near-sighted
• Locality in Distributed Graph Algorithms
• 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
• Distributed Computing: A Locality-Sensitive Approach
• What Can be Computed Locally?
• An efficient distributed algorithm for constructing small dominating sets
• Hundreds of impossibility results for distributed computing
• On the locality of bounded growth
• What cannot be computed locally!
• Approximation and Online Algorithms
• Constant-time distributed dominating set approximation

This page was built for publication: Local Algorithms for Dominating and Connected Dominating Sets of Unit Disk Graphs with Location Aware Nodes