Local Algorithms for Dominating and Connected Dominating Sets of Unit Disk Graphs with Location Aware Nodes
From MaRDI portal
Publication:5458525
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
Dominating setConnected dominating setLocation awarenessApproximation factorLocal algorithmUnit disk graph
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