Article ID: | iaor20114247 |
Volume: | 60 |
Issue: | 2 |
Start Page Number: | 236 |
End Page Number: | 249 |
Publication Date: | Jun 2011 |
Journal: | Algorithmica |
Authors: | Bose Prosenjit, Kranakis Evangelos, Barbeau Michel, Carmi Paz, Couture Mathieu |
Keywords: | simulation: applications |
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/