Location-oblivious distributed unit disk graph coloring

DOI10.1007/s00453-009-9334-zzbMath1215.68167OpenAlexW2091923232MaRDI QIDQ534767

Michel Barbeau, Mathieu Couture, Prosenjit Bose, Evangelos Kranakis, Paz Carmi

Publication date: 10 May 2011

Published in: Algorithmica (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/s00453-009-9334-z

zbMATH Keywords

coloringapproximation algorithmsdistributed algorithmsunit disk graphlocation-oblivious algorithms

Mathematics Subject Classification ID

Graph theory (including graph drawing) in computer science (68R10) Coloring of graphs and hypergraphs (05C15) Approximation algorithms (68W25) Distributed algorithms (68W15)

Cites Work

• Unit disk graph recognition is NP-hard
• On coloring unit disk graphs
• The on-line first-fit algorithm for radio frequency assignment problems.
• Design and Analysis of Distributed Algorithms
• Smallest-last ordering and clustering and graph coloring algorithms
• Robust algorithms for restricted domains
• Simple heuristics for unit disk graphs
• Independence and Coloring Problems on Intersection Graphs of Disks

This page was built for publication: Location-oblivious distributed unit disk graph coloring