caa a22 4500 445804653 CHVBK 20180317145153.0 cr unu---uuuuu 170323e20110601xx s 000 0 eng 10.1007/s00453-009-9334-z doi (NATIONALLICENCE)springer-10.1007/s00453-009-9334-z Location-Oblivious Distributed Unit Disk Graph Coloring [Elektronische Daten] [Michel Barbeau, Prosenjit Bose, Paz Carmi, Mathieu Couture, Evangelos Kranakis] 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. Springer Science+Business Media, LLC, 2009 Coloring nationallicence Unit disk graph nationallicence Approximation algorithms nationallicence Distributed algorithms nationallicence Location oblivious algorithms nationallicence Barbeau Michel School of Computer Science, Carleton University, Ottawa, Ontario, Canada aut Bose Prosenjit School of Computer Science, Carleton University, Ottawa, Ontario, Canada aut Carmi Paz School of Computer Science, Carleton University, Ottawa, Ontario, Canada aut Couture Mathieu School of Computer Science, Carleton University, Ottawa, Ontario, Canada aut Kranakis Evangelos School of Computer Science, Carleton University, Ottawa, Ontario, Canada aut Algorithmica Springer-Verlag 60/2(2011-06-01), 236-249 0178-4617 60:2<236 2011 60 453 https://doi.org/10.1007/s00453-009-9334-z text/html Onlinezugriff via DOI 1 research-article jats NATIONALLICENCE 856 40 https://doi.org/10.1007/s00453-009-9334-z text/html Onlinezugriff via DOI NATIONALLICENCE 700 1- Barbeau Michel School of Computer Science, Carleton University, Ottawa, Ontario, Canada aut NATIONALLICENCE 700 1- Bose Prosenjit School of Computer Science, Carleton University, Ottawa, Ontario, Canada aut NATIONALLICENCE 700 1- Carmi Paz School of Computer Science, Carleton University, Ottawa, Ontario, Canada aut NATIONALLICENCE 700 1- Couture Mathieu School of Computer Science, Carleton University, Ottawa, Ontario, Canada aut NATIONALLICENCE 700 1- Kranakis Evangelos School of Computer Science, Carleton University, Ottawa, Ontario, Canada aut NATIONALLICENCE 773 0- Algorithmica Springer-Verlag 60/2(2011-06-01), 236-249 0178-4617 60:2<236 2011 60 453 Metadata rights reserved Springer special CC-BY-NC licence nationallicence BK010053 XK010053 XK010000 NATIONALLICENCE NATIONALLICENCE NL-springer