Online Graph Edge-Coloring in the Random-Order Arrival Model

by Bahman Bahmani, Aranyak Mehta, and Rajeev Motwani

Theory of Computing, Volume 8(25), pp. 567-595, 2012

Bibliography with links to cited articles

[1]   Gagan Aggarwal, Rajeev Motwani, Devavrat Shah, and An Zhu: Switch scheduling via randomized edge coloring. In Proc. 44th FOCS, pp. 502–512. IEEE Comp. Soc. Press, 2003. [doi:10.1109/SFCS.2003.1238223]

[2]   Amotz Bar-Noy, Rajeev Motwani, and Joseph Naor: The greedy algorithm is optimal for on-line edge coloring. Inform. Process. Lett., 44(5):251–253, 1992. [doi:10.1016/0020-0190(92)90209-E]

[3]   Richard Cole, Kirstin Ost, and Stefan Schirra: Edge-coloring bipartite multigraphs in O(E log D) time. Combinatorica, 21(1):5–12, 2001. [doi:10.1007/s004930170002]

[4]   Devdatt Dubhashi, David A. Grable, and Alessandro Panconesi: Near-optimal, distributed edge colouring via the nibble method. Theoret. Comput. Sci., 203(2):225–251, 1998. Preliminary version in ESA’95. [doi:10.1016/S0304-3975(98)00022-X]

[5]   Devdatt Dubhashi and Alessandro Panconesi: Concentration of measure for the analysis of randomized algorithms. Cambridge University Press, New York, NY, USA, 1st edition, 2009.

[6]   David A. Grable and Alessandro Panconesi: Nearly optimal distributed edge coloring in o(log log n) rounds. Random Structures Algorithms, 10(3):385–405, 1997. Preliminary version in SODA’97. [doi:10.1002/(SICI)1098-2418(199705)10:3¡385::AID-RSA6¿3.0.CO;2-S]

[7]   Ian Holyer: The NP-completeness of edge-coloring. SIAM J. Comput., 10(4):718–720, 1981. [doi:10.1137/0210055]

[8]   Alessandro Panconesi and Aravind Srinivasan: Randomized distributed edge coloring via an extension of the Chernoff-Hoeffding bounds. SIAM J. Comput., 26(2):350–368, 1997. Preliminary version in PODC’92. [doi:10.1137/S0097539793250767]

[9]   Vadim G. Vizing: On an estimate of the chromatic class of a p-graph. Metody Diskret. Analiz., 3:25–30, 1964.