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

zbMATH Keywords

Dominating setConnected dominating setLocation awarenessApproximation factorLocal algorithmUnit disk graph

Mathematics Subject Classification ID

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

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

Cites work

• scientific article; zbMATH DE number 5605099 (Why is no real title available?)
• A polynomial-time approximation scheme for the minimum-connected dominating set in ad hoc wireless networks
• An efficient distributed algorithm for constructing small dominating sets
• Approximation algorithms for combinatorial problems
• Approximation and Online Algorithms
• Broadcasting in geometric radio networks
• Constant-time distributed dominating set approximation
• Discrete mobile centers
• Distributed Computing: A Locality-Sensitive Approach
• Hundreds of impossibility results for distributed computing
• Local Construction of Planar Spanners in Unit Disk Graphs with Irregular Transmission Ranges
• Locality in Distributed Graph Algorithms
• NC-Approximation Schemes for NP- and PSPACE-Hard Problems for Geometric Graphs
• On approximating the minimum independent dominating set
• On the hardness of approximating minimization problems
• On the locality of bounded growth
• The price of being near-sighted
• Unit disk graph recognition is NP-hard
• Unit disk graphs
• What Can be Computed Locally?
• What cannot be computed locally!

Cited in

(8)

• Analysing local algorithms in location-aware quasi-unit-disk graphs
• Impact of locality on location aware unit disk graphs
• An efficient sum query algorithm for distance-based locally dominating functions
• A self-stabilizing 6-approximation for the minimum connected dominating set with safe convergence in unit disk graphs
• Approximation and heuristic algorithms for computing backbones in asymmetric ad-hoc networks
• An asynchronous self-stabilizing approximation for the minimum CDS with safe convergence in UDGs
• The expected size of the Rule \(k\) dominating set
• Local PTAS for Dominating and Connected Dominating Set in Location Aware Unit Disk Graphs

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)