Location-oblivious distributed unit disk graph coloring

DOI10.1007/S00453-009-9334-ZMaRDI QIDQ534767zbMATH OpenOpenAlexFDO

Authors Michel Barbeau, Prosenjit Bose, Paz Carmi, M. Couture, Evangelos Kranakis

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

approximation algorithmsdistributed algorithmscoloringunit disk graphlocation-oblivious algorithms

Mathematics Subject Classification ID

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

Recommendations

• Location Oblivious Distributed Unit Disk Graph Coloring
• Distributed coloring and the local structure of unit-disk graphs
• Distributed coloring and the local structure of unit-disk graphs
• Local construction and coloring of spanners of location aware unit disk graphs
• On coloring unit disk graphs

Cites work

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

Cited in

(3)

• Location Oblivious Distributed Unit Disk Graph Coloring
• Distributed coloring and the local structure of unit-disk graphs
• Distributed coloring and the local structure of unit-disk graphs

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

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