Location-oblivious distributed unit disk graph coloring

DOI10.1007/S00453-009-9334-ZzbMATH Open1215.68167OpenAlexW2091923232MaRDI QIDQ534767FDOQ534767

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

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

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)

Cites Work

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

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)