LOCAL CONSTRUCTION AND COLORING OF SPANNERS OF LOCATION AWARE UNIT DISK GRAPHS

DOI10.1142/S1793830909000415zbMath1194.05046MaRDI QIDQ5189993

Andreas Wiese, Evangelos Kranakis

Publication date: 11 March 2010

Published in: Discrete Mathematics, Algorithms and Applications (Search for Journal in Brave)

zbMATH Keywords

coloringapproximation algorithmsspannerlocal algorithmsunit disk graphs

Mathematics Subject Classification ID

Coloring of graphs and hypergraphs (05C15) Graph algorithms (graph-theoretic aspects) (05C85) Approximation algorithms (68W25) Distributed algorithms (68W15)

Related Items (4)

Local Construction and Coloring of Spanners of Location Aware Unit Disk Graphs ⋮ Analysing local algorithms in location-aware quasi-unit-disk graphs ⋮ Distributed coloring and the local structure of unit-disk graphs ⋮ Distributed coloring and the local structure of unit-disk graphs

Cites Work

• Unit disk graphs
• A proof of the four color theorem
• On coloring unit disk graphs
• Local solutions for global problems in wireless networks
• Locality in Distributed Graph Algorithms
• On the hardness of approximating minimization problems
• Approximating the Stretch Factor of Euclidean Graphs
• Simple heuristics for unit disk graphs
• Routing with guaranteed delivery in ad hoc wireless networks

This page was built for publication: LOCAL CONSTRUCTION AND COLORING OF SPANNERS OF LOCATION AWARE UNIT DISK GRAPHS