Local PTAS for Dominating and Connected Dominating Set in Location Aware Unit Disk Graphs

DOI10.1007/978-3-540-93980-1_18zbMath1209.68655OpenAlexW2416485279MaRDI QIDQ3602842

Andreas Wiese, Evangelos Kranakis

Publication date: 12 February 2009

Published in: Approximation and Online Algorithms (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/978-3-540-93980-1_18

Mathematics Subject Classification ID

Graph algorithms (graph-theoretic aspects) (05C85) Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) (05C69) Approximation algorithms (68W25)

Related Items (5)

Impact of locality on location aware unit disk graphs ⋮ Distributed minimum dominating set approximations in restricted families of graphs ⋮ Analysing local algorithms in location-aware quasi-unit-disk graphs ⋮ Leveraging Linial’s Locality Limit ⋮ Local PTAS for Dominating and Connected Dominating Set in Location Aware Unit Disk Graphs

Cites Work

• Unnamed Item
• Unit disk graphs
• Unit disk graph recognition is NP-hard
• The price of being near-sighted
• Local PTAS for Dominating and Connected Dominating Set in Location Aware Unit Disk Graphs
• Locality in Distributed Graph Algorithms
• 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
• On the locality of bounded growth
• Distributed Computing
• A randomized distributed algorithm for the maximal independent set problem in growth-bounded graphs
• Local Algorithms for Dominating and Connected Dominating Sets of Unit Disk Graphs with Location Aware Nodes
• Approximation and Online Algorithms

This page was built for publication: Local PTAS for Dominating and Connected Dominating Set in Location Aware Unit Disk Graphs