Compute Canada

View All Papers
To Submit a new publication, Please visit the User's Section (logged in users only)

Publications:

To view a publication's Abstract (if available), click on publication's title

Author(s)

     Mathieu Couture, Michel Barbeau, Prosenjit Bose, Paz Carmi, Evangelos Kranakis

Title

     Location Oblivious Distributed Unit Disk Graph Coloring

Publication Name

     14th International Colloquium on Structural Information and Communication Complexity (SIROCCO)

Publication Type

     
Publisher
     Springer
Place
      Castiglioncello (LI), Italy
Editor(s)
     
Number
     
School
      Scool of Computer Science, Carleton University
Volume
     
Chapter
     
Pages
     
Other Publication Information
     
Publication Year
     2007
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 since we present a new lower bound of 10/3 for the worst-case performance ratio of the sequential coloring algorithm. The previous greatest lower bound on the performance ratio of the sequential coloring algorithm was 5/2. Using simulation, we also compare our algorithm with other existing unit disk graph coloring algorithms.
Keywords
     coloring, unit disk graph, approximation algorithms, distributed algorithms, location oblivious algorithms
Website
     http://cg.scs.carleton.ca/~mathieu/publications.html
Paper Status
     Published
DOI / Publication ID
     



View All Papers