Location‐Oblivious Distributed Unit Disk Graph Coloring

Location‐Oblivious Distributed Unit Disk Graph Coloring

0.00 Avg rating0 Votes
Article ID: iaor20114247
Volume: 60
Issue: 2
Start Page Number: 236
End Page Number: 249
Publication Date: Jun 2011
Journal: Algorithmica
Authors: , , , ,
Keywords: simulation: applications
Abstract:

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) . 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.

Reviews

Required fields are marked *. Your email address will not be published.