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.