Impact of locality on location aware unit disk graphs

DOI10.3390/A1010002MaRDI QIDQ1662429zbMATH OpenOpenAlexFDO

Authors Andreas Wiese, Evangelos Kranakis

Publication date 20 August 2018

Published in Algorithms (Search for Journal in Brave)

Copyright license Creative Commons Attribution 4.0 International

Full work available at URL https://doi.org/10.3390/a1010002

zbMATH Keywords

approximation algorithmslocal algorithmslocation awarenesslower boundsunit disk graphs

Mathematics Subject Classification ID

Network design and communication in computer systems (68M10) Communication networks in operations research (90B18) Discrete location and assignment (90B80)

Review text

Summary: Due to their importance for studies oi wireless networks, recent years have seen a surge of activity on the design of local algorithms for the solution of a variety of network tasks. We study the behaviour of algorithms with very low localities. Despite of this restriction we propose local constant ratio approximation algorithms for solving minimum dominating and connected dominating set, maximum independent set and minimum vertex cover in location aware Unit Disk Graphs. We also prove the first ever lower bounds for local algorithms for these problems with a given locality in the location aware setting.

Recommendations

• Local PTAS for Dominating and Connected Dominating Set in Location Aware Unit Disk Graphs
• Local Algorithms for Dominating and Connected Dominating Sets of Unit Disk Graphs with Location Aware Nodes
• Analysing local algorithms in location-aware quasi-unit-disk graphs
• Local solutions for global problems in wireless networks
• Local Construction and Coloring of Spanners of Location Aware Unit Disk Graphs

Cites work

• A randomized distributed algorithm for the maximal independent set problem in growth-bounded graphs
• Approximation and Online Algorithms
• Distributed Computing: A Locality-Sensitive Approach
• Graph-Theoretic Concepts in Computer Science
• scientific article; zbMATH DE number 3889282 (Why is no real title available?)
• scientific article; zbMATH DE number 3639144 (Why is no real title available?)
• scientific article; zbMATH DE number 1559563 (Why is no real title available?)
• Local Algorithms for Dominating and Connected Dominating Sets of Unit Disk Graphs with Location Aware Nodes
• 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
• Simple heuristics for unit disk graphs
• Unit disk graphs
• What can be computed locally?

Cited in

(5)

• Local PTAS for Dominating and Connected Dominating Set in Location Aware Unit Disk Graphs
• On the locality of bounded growth
• Local Algorithms for Dominating and Connected Dominating Sets of Unit Disk Graphs with Location Aware Nodes
• Weak models of distributed computing, with connections to modal logic
• Analysing local algorithms in location-aware quasi-unit-disk graphs

This page was built for publication: Impact of locality on location aware unit disk graphs

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1662429)