On graph coloring in a~class of parallel local algorithms

V. A. Evstigneev ; Y. Tursunbay kyzy

Sibirskij žurnal vyčislitelʹnoj matematiki, Tome 14 (2011) no. 3, pp. 231-243.

Résumé

One of the ways for improving the performance of a distributed algorithm is representation of the coloring strategy into the algorithm which, as known, is efficient in non-distributed algorithms. In this paper we show that application of a certain sequential coloring algorithm heuristics such as the largest-first (SL), the smallest-last (SL) and the saturation largest-first (SLF) for some classes of graphs and for special cases of the vertex coloring in the distributed algorithms give us optimal or near-optimal coloring.

Bibliographie

[1] Zhuravlev Yu. I., “Lokalnye algoritmy vychisleniya informatsii”, Kibernetika, 1965, no. 1, 12–19 | MR | Zbl

[2] Zhuravlev Yu. I., “Algoritmy postroeniya minimalnykh diz'yunktivnykh normalnykh form dlya funktsii algebry logiki”, Diskretnaya matematika i matematicheskie voprosy kibernetiki, v. 1, Nauka, M., 1974, 67–98

[3] Averbuch B., “A new distributed depth-first-search algorithm”, Inf. Process. Lett., 20:3 (1985), 147–150 | DOI

[4] Chandy K. M., Mistra J., “Distributed computation on graphs: shortest path algorithms”, Com. ACM, 25:11 (1982), 833–837 | DOI | MR | Zbl

[5] Chang E. J. H., “Echo-algorithms: depth parallel operations on general graphs”, IEEE Trans. On Software Eng., SE-8:4 (1982), 391–401 | DOI

[6] Herman T., Chandy K. M., “On distributed search”, Inf. Process. Lett., 21:8 (1985), 666–677 | MR

[7] Evstigneev V. A., “O nekotorykh svoistvakh lokalnykh algoritmov na grafakh”, Kombinatorno-algebraicheskie metody v prikladnoi matematike, Izd-vo GGU, Gorkii, 1983, 72–105 | MR

[8] Evstigneev V. A., “Lokalnyi algoritm otyskaniya bikomponent v orientirovannom grafe”, ZhVM, 18:5 (1978), 1345–1349 | MR | Zbl

[9] Evstigneev V. A., “Lokalnye vychislitelnye algoritmy i nakhozhdenie vershin s naibolshei stepenyu v neorientirovannom grafe”, Kombinatorno-algebraicheskie metody v prikladnoi matematike, Izd-vo GGU, Gorkii, 1981, 60–66 | MR

[10] Dijastra E. W., Scholton C. S., “Termination detection for diffusing computations”, Inf. Process. Lett., 11:1 (1980), 1–4 | DOI | MR

[11] Evstigneev V. A., “Lokalnye algoritmy na grafakh i problema detsentralizovannoi obrabotki informatsii”, Tez. dokl. II Vsesoyuz. konf. po prikladnoi logike, Novosibirsk, 1988, 75–77

[12] Evstigneev V. A., “Lokalnye algoritmy i raspredelennye vychisleniya”, Tez. dokl. VIII Vsesoyuz. konf. “Problemy teoreticheskoi kibernetiki”, Gorkii, 1988, 113–114

[13] Battiti R., Bertossi A. A., Bonuccelli M. A., “Assigning codes in wireless networks”, Wireless Networks, 1999, no. 5, 195–209 | DOI

[14] Evstigneev V. A., Primenenie teorii grafov v programmirovanii, Nauka, M., 1985 | MR

[15] Emelichev V. A., Melnikov O. I., Sarvanov V. I., Tyshkevich R. I., Lektsii po teorii grafov, Nauka, M., 1990 | MR | Zbl

[16] Bellare M., Goldreich O., Sudan M., “Free bits, PCPs and non-approximability – towards tight results”, SIAM J. Comp., 27 (1998), 804–915 | DOI | MR | Zbl

[17] Johansson Ö., “Simple distributed $\Delta+1$-coloring of graphs”, Inf. Process. Lett., 70 (1999), 229–232 | DOI | MR | Zbl

[18] Grable D. A., Panconesi A., “Fast distributed algorithms for Brooks–Vizing colorings”, J. Algorithms, 37 (2000), 85–120 | DOI | MR | Zbl

[19] Cole R., Vishkin U., “Deterministic coin tossing with applications to optimal parallel list ranking”, Inf. Control., 70:1 (1986), 32–53 | DOI | MR | Zbl

[20] Goldberg A. V., Plotkin S. A., “Parallel $\Delta+1$-coloring of constant-degree graphs”, Information Processing Lett., 25 (1987), 241–245 | DOI | MR | Zbl

[21] Panconesi A., Rizzi R., “Some simple distributed algorithms for sparse networks”, Distributed Computing, 14:2 (2001), 97–100 | DOI

[22] Goldberg A., Plotkin S., Shannon G., “Parallel symmetry-breaking in sparse graphs”, Proc. of the 19th Annual ACM Conf. on Theory of Computing (STOC), 1987, 315–324

[23] Grable D. A., Panconesi A., “Fast distributed algorithms for Brooks–Vizing colorings”, Proc. of the 9th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), 1998, 473–480 | MR | Zbl

[24] Hansen J., Kubale M., Kuszner L., Nadolski A., “Distributed largest-first algorithm for graph coloring”, Proc. of Euro-Par., Lect. Notes Comp. Sci., 3149, Springer-Verlag, 2004, 527–539

[25] Panconesi A., Silvestri R., “Experimental analysis of simple, distributed vertex coloring algorithms”, Proc. of the 13th ACM-SIAM Symposium on Discrete Algorithms (SODA), 2002, 606–615 | Zbl

[26] Szekeres G., Wilf H. S., “An inequality for the chromatic number of a graph”, J. Combin. Theory, 4 (1964), 1–3 | MR

[27] Voloshin V. I., “Svoistvo triangulirovannykh grafov”, Issled. operatsii i programmirovaniya mat. nauk, Kishinev, 1982, 24–32 | MR | Zbl

[28] Markosyan S. E., Gasparyan G. S., “$w$-sovershennye grafy”, Uchenye zapiski, 3, Erevanskii gosuniversit, Erevan, 1987, 9–15 | MR | Zbl

[29] Evstigneev V. A., “Khordalnye grafy i ikh svoistva”, Problemy sistem informatiki i programmirovaniya, Novosibirsk, 1999, 33–64

[30] Matula D. W., Bleck L. L., “Smallest-last ordering and dustering and graph coloring algorithms”, J. Assoc. Comput. Math., 30:3 (1983), 417–427 | MR | Zbl

[31] Hale W. K., “Frequency assignment: theory and applications”, Proc. of the IEEE, 68:12 (1980), 1497–1514 | DOI

[32] Cozzens M. B., Roberts F. S., “$T$-colorings of graphs and the channel assignment problem”, Congressus Numerantium, 35 (1982), 191–208 | MR

[33] Simon H. U., “Approximation algorithms for channel assignment in cellular radio networks”, Fundamentals of Computation Theory, Lect. Notes Comp. Sci., 380, Springer-Verlag, 1989, 405–415 | MR

[34] Roberts F. S., “$T$-colorings of graphs: Recent results and open problems”, Discrete Mathematics, 93:2–3 (1991), 229–245 | DOI | MR | Zbl

[35] Tesman B. A., “Set $T$-colorings”, Congressus Numerantium, 77 (1990), 229–242 | MR | Zbl

[36] Brelaz D., “New methods to color the vertices of a graph”, Communications of the ACM, 22:4 (1979), 251–256 | DOI | MR | Zbl

[37] Costa D., “On the use of some known methods for $T$-colorings of graphs”, Annals of Operations Research, 41:4 (1993), 343–358 | DOI | Zbl

[38] Kosowski A., Kuszner L., “On greedy graph coloring in the distributed model”, Proc. of Euro-Par., Lect. Notes Comp. Sci., 4128, Springer-Verlag, Drezden, 2006, 592–601

[39] Kubika E., The chromatic sum of a graph, Ph. D. dissertation, Western Michigan University, Michigan, 1989

[40] Supowit K. J., “Finding a maximum planar subset of nets in a channel”, IEEE Trans. on Computer Aided Design (CAD), 6:1 (1987), 93–94 | DOI

[41] Nicolosco S., Sarrafzadeh M., Song X., “On the sum coloring problem on interval graphs”, Algorithmica, 23 (1999), 109–126 | DOI | MR