Abstract
This paper develops a distributed algorithm to color the edges of a bipartite network in such a way that any two adjacent edges receive distinct colors. The algorithm has the self-stabilizing property. It works with an arbitrary initialization. Its execution model is assumed to be the central daemon, and its time complexity is O(n 2 m) moves, where n and m are the number of nodes and the number of edges, respectively.
This research was supported in part by the National Science Council of the Republic of China under the Contract NSC94-2213-E008-001.
This is a preview of subscription content, log in via an institution to check access.
Preview
Unable to display preview. Download preview PDF.
Similar content being viewed by others
References
Dijkstra, E.W.: Self-stabilizing systems in spite of distributed control. Communications of the ACM 17, 643–644 (1974)
Dolev, S.: Self-stabilization. MIT Press, Cambridge (2000)
Durand, D., Jain, R., Tseytlin, D.: Parallel I/O scheduling using randomized, distributed edge coloring algorithms. Journal of parallel and distributed computing 63, 611–618 (2003)
Herman, T., Pirwani, I., Pemmaraju, S.: Oriented edge colorings and link scheduling in sensor networks. In: International Conference on communication Software and Middleware, pp. 1–6 (2006)
König, D.: Über graphen und ihre anwendung auf determinententheorie und mengenlehre. Math. Ann 77, 453–465 (1916)
Gabow, H.N., Kariv, O.: Algorithms for edge coloring bipartite graphs. In: Conference of the 10th annual ACM symposium on theory of computing, pp. 184–192 (1978)
Gabow, H.N., Kariv, O.: Algorithms for edge coloring bipartite graphs and multigraphs. SIAM Journal on Computing 11(1), 117–129 (1982)
Schrijver, A.: Bipartite edge coloring in O(Δm) time. SIAM Journal on Computing 28, 841–846 (1999)
Cole, R., Ost, K., Schirra, S.: Edge-coloring bipartite multigraphs in O(E logD) time. Combinatorica 21(1), 5–12 (2001)
Grable, D., Panconesi, A.: Nearly optimal distributed edge-coloring in O(loglogn) rounds. RSA 10(3), 385–405 (1997)
Panconesi, A., Srinivasan, A.: Fast randomized algorithms for distributed edge coloring. SIAM Journal on Computing 26(2), 350–368 (1992)
Sakurai, Y., Ooshita, F., Masuzawa, T.: A Self-stabilizing Link-Coloring Protocol Resilient to Byzantine Faults in Tree Networks. In: Higashino, T. (ed.) OPODIS 2004. LNCS, vol. 3544, pp. 283–298. Springer, Heidelberg (2005)
Masuzawa, T., Tixeuil, S.: A self-stabilizing link coloring algorithm resilient to unbounded byzantine faults in arbitrary networks. Technical report, Laboratoire de Recherche en Informatique (2005)
Chattopadhyay, S., Higham, L., Seyffarth, K.: Dynamic and self-stabilizing distributed matching. In: ACM symposium on principles of distributed computing, pp. 290–297 (2002)
Hsu, S.C., Huang, S.T.: A self-stabilizing algorithm for maximal matching. Information processing letters 24, 77–81 (1992)
Karaata, M.H., Saleh, K.A.: A distributed self-stabilizing algorithm for finding maximum matching. Computer systems science and engineering 3, 175–180 (2000)
Rizzi, R.: Konig’s edge coloring theorem without augmenting paths. Journal of graph theory 29, 87 (1998)
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2006 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Huang, ST., Tzeng, CH. (2006). Distributed Edge Coloration for Bipartite Networks. In: Datta, A.K., Gradinariu, M. (eds) Stabilization, Safety, and Security of Distributed Systems. SSS 2006. Lecture Notes in Computer Science, vol 4280. Springer, Berlin, Heidelberg. https://doi.org/10.1007/978-3-540-49823-0_26
Download citation
DOI: https://doi.org/10.1007/978-3-540-49823-0_26
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-540-49018-0
Online ISBN: 978-3-540-49823-0
eBook Packages: Computer ScienceComputer Science (R0)