Local Algorithms for Dominating and Connected Dominating Sets of Unit Disk Graphs with Location Aware Nodes
DOI10.1007/978-3-540-78773-0_14zbMATH Open1136.68453OpenAlexW25150355MaRDI QIDQ5458525FDOQ5458525
Authors:
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
Recommendations
- Local PTAS for Dominating and Connected Dominating Set in Location Aware Unit Disk Graphs
- Impact of locality on location aware unit disk graphs
- Constant-Factor Approximation for Minimum-Weight (Connected) Dominating Sets in Unit Disk Graphs
- Analysing local algorithms in location-aware quasi-unit-disk graphs
- A polynomial-time approximation scheme for the minimum-connected dominating set in ad hoc wireless networks
Dominating setConnected dominating setLocation awarenessApproximation factorLocal algorithmUnit disk graph
Graph algorithms (graph-theoretic aspects) (05C85) Graph theory (including graph drawing) in computer science (68R10) Network protocols (68M12)
Cites Work
- Approximation algorithms for combinatorial problems
- Unit disk graphs
- Unit disk graph recognition is NP-hard
- Distributed Computing: A Locality-Sensitive Approach
- On approximating the minimum independent dominating set
- Locality in Distributed Graph Algorithms
- Hundreds of impossibility results for distributed computing
- What cannot be computed locally!
- On the hardness of approximating minimization problems
- Discrete mobile centers
- A polynomial-time approximation scheme for the minimum-connected dominating set in ad hoc wireless networks
- NC-Approximation Schemes for NP- and PSPACE-Hard Problems for Geometric Graphs
- Constant-time distributed dominating set approximation
- Broadcasting in geometric radio networks
- Approximation and Online Algorithms
- On the locality of bounded growth
- An efficient distributed algorithm for constructing small dominating sets
- The price of being near-sighted
- What Can be Computed Locally?
- Local Construction of Planar Spanners in Unit Disk Graphs with Irregular Transmission Ranges
- Title not available (Why is that?)
Cited In (8)
- Approximation and heuristic algorithms for computing backbones in asymmetric ad-hoc networks
- A self-stabilizing 6-approximation for the minimum connected dominating set with safe convergence in unit disk graphs
- The expected size of the Rule \(k\) dominating set
- Local PTAS for Dominating and Connected Dominating Set in Location Aware Unit Disk Graphs
- Impact of locality on location aware 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
- An efficient sum query algorithm for distance-based locally dominating functions
This page was built for publication: Local Algorithms for Dominating and Connected Dominating Sets of Unit Disk Graphs with Location Aware Nodes
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5458525)
