×

Location-oblivious distributed unit disk graph coloring. (English) Zbl 1215.68167

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

Citations:

Zbl 1042.68096
PDFBibTeX XMLCite
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.