Barbeau, Michel; Bose, Prosenjit; Carmi, Paz; Couture, Mathieu; Kranakis, Evangelos Location-oblivious distributed unit disk graph coloring. (English) Zbl 1215.68167 Algorithmica 60, No. 2, 236-249 (2011). Summary: 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) [Y.-T. Tsai, Y.-L. Lin, and F. R. Hsu, “The on-line first-fit algorithm for radio frequency assignment problems”, Inf. Process. Lett. 84, No.4, 195–199 (2002; Zbl 1042.68096)]. 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. MSC: 68R10 Graph theory (including graph drawing) in computer science 68W15 Distributed algorithms 68W25 Approximation algorithms 05C15 Coloring of graphs and hypergraphs Keywords:coloring; unit disk graph; approximation algorithms; distributed algorithms; location-oblivious algorithms Citations:Zbl 1042.68096 PDFBibTeX XMLCite \textit{M. Barbeau} et al., Algorithmica 60, No. 2, 236--249 (2011; Zbl 1215.68167) Full Text: DOI References: [1] Breu, H., Kirkpatrick, D.G.: Unit disk graph recognition is np-hard. Comput. Geom. Theory Appl. 9(1–2), 3–24 (1998) · Zbl 0894.68099 [2] Erlebach, T., Fiala, J.: Independence and coloring problems on intersection graphs of disks. In: Approximation Algorithms in Combinatorial Optimization. Lecture Notes in Computer Science, vol. 3484, pp. 135–155. Springer, Berlin (2006) · Zbl 1132.68819 [3] Gräf, A., Stumpf, M., Weißenfels, G.: On coloring unit disk graphs. Algorithmica 20(3), 277–293 (1998) · Zbl 0901.68152 [4] Hale, W.K.: Frequency assignment: theory and applications. In: Proceedings of the IEEE, vol. 68, pp. 1497–1514 (1980) [5] Karp, R.M.: Reducibility among combinatorial problems. In: Miller, R.E., Thatcher, J.W. (eds.) Complexity of Computer Computations, pp. 85–103. Plenum, New York (1972) [6] Marathe, M., Breu, H., Ravi, S., Rosenkrantz, D.: Simple heuristics for unit disk graphs. Networks 25, 59–68 (1995) · Zbl 0821.90128 [7] Matula, D.W., Beck, L.L.: Smallest-last ordering and clustering and graph coloring algorithms. J. ACM 30(3), 417–427 (1983) · Zbl 0628.68054 [8] Peeters, R.: On coloring j-unit sphere graphs. Technical Report FEW 512, Department of Economics, Tilburg University, Tilburg, The Netherlands (1991) [9] Raghavan, V., Spinrad, J.: Robust algorithms for restricted domains. J. Algorithms 48(1), 160–172 (2003) · Zbl 1079.68110 [10] Santoro, N.: Design and Analysis of Distributed Algorithms. Wiley, New York (2006) · Zbl 1115.68166 [11] Tsai, Y., Lin, Y., Hsu, F.: The online first-fit algorithm for radio frequency assignment problems. Inf. Process. Lett. 84(4), 195–199 (2002) · Zbl 1042.68096 This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.