We present the first location-oblivious distributed unit disk graph coloring algorithm having a provable performance ratio of three (i.e. the number of colors used by the algorithm is at most three times the chromatic number of the graph). This is an improvement over the standard sequential coloring algorithm that has a worst case lower bound on its performance ratio of 4-3/k (for any k>2, where k is the chromatic number of the unit disk graph achieving the lower bound) (Tsai et al., in Inf. Process. Lett. 84(4):195-199, 2002). We present a slightly better worst case lower bound on the performance ratio of the sequential coloring algorithm for unit disk graphs with chromatic number 4. Using simulation, we compare our algorithm with other existing unit disk graph coloring algorithms.

Additional Metadata
Keywords Approximation algorithms, Coloring, Distributed algorithms, Location oblivious algorithms, Unit disk graph
Persistent URL dx.doi.org/10.1007/s00453-009-9334-z
Journal Algorithmica
Citation
Barbeau, M, Bose, P, Carmi, P. (Paz), Couture, M. (Mathieu), & Kranakis, E. (2011). Location-oblivious distributed unit disk graph coloring. Algorithmica, 60(2), 236–249. doi:10.1007/s00453-009-9334-z