Local Construction and Coloring of Spanners of Location Aware Unit Disk Graphs

DOI10.1007/978-3-540-92248-3_33zbMath1202.05048OpenAlexW1484713053MaRDI QIDQ5302070

Andreas Wiese, Evangelos Kranakis

Publication date: 20 January 2009

Published in: Graph-Theoretic Concepts in Computer Science (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/978-3-540-92248-3_33

zbMATH Keywords

graph spannersunit disk graphscoloring spanners

Mathematics Subject Classification ID

Trees (05C05) Graph theory (including graph drawing) in computer science (68R10) Coloring of graphs and hypergraphs (05C15) Approximation algorithms (68W25) Graph representations (geometric and intersection representations, etc.) (05C62)

Related Items (1)

Analysing local algorithms in location-aware quasi-unit-disk graphs

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unit disk graphs
• A proof of the four color theorem
• Zero knowledge and the chromatic number
• On coloring unit disk graphs
• Efficient Construction of Low Weight Bounded Degree Planar Spanner
• Local 7-Coloring for Planar Subgraphs of Unit Disk Graphs
• Local Construction of Planar Spanners in Unit Disk Graphs with Irregular Transmission Ranges
• 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
• LOCAL CONSTRUCTION AND COLORING OF SPANNERS OF LOCATION AWARE UNIT DISK GRAPHS
• What can be computed locally?
• 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