A self-stabilizing algorithm for edge-coloring of graphs

• Autorzy: Kuszner Ł. , Nadolski A.
• Języki publikacji: EN

Słowa kluczowe

EN

distributed algorithm; edge colouring; self-stabilization

• Wydawca: Wydawnictwo Politechniki Poznańskiej
• Czasopismo: Foundations of Computing and Decision Sciences
• Rocznik: 2006
• Tom: Vol. 31, No. 2
• Strony: 158--167
• Opis fizyczny: Bibliogr. 21 poz.

Twórcy

autor

Kuszner Ł.

autor

Nadolski A.

• Gdańsk University of Technology, Department of Algorithms and System Modeling, Narutowicza 11/12, 80-952 Gdańsk, Poland,

Bibliografia

• [1] Axenovich M., A note on graph coloring extensions and list colorings, Electronic Journal of Combinatorics, Note, 10, 2003, available at http : //www.combinatorics.org/VolumeiQ/vlOiltoc.html.
• [2] Bodlaender H. L., Jansen K., Woeginger G. J., Scheduling with incompatible jobs, Discrete Appl. Math., 55, 1994, 219-232.
• [3] S. C. Bruell, S. Ghosh, M. H. Kaxaata, and S. V. Pemmaraju: Self-stabilizing algorithms for finding centers and medians of trees. SIAM J. Comput. 29, 1999, 600-614.
• [4] A. Czygrinow, M. Hańćkowiak and M. Karonski: Distributed O(Alog(n))-edge-coloring algorithm, ESA, 2001, 345-355.
• [5] S. Dolev: Self-Stabilization. MIT Press, 2000.
• [6] E. W. Dijksjra: Self-stabilizing systems in spite of distributed control. Communication of the ACM 17, 1974, 643-644.
• [7] S. Ghosh and M. H. Karaata: A self-stabilizing algorithm for coloring planar graphs. Distributed Computing 7, 1993, 55-59.
• [8] S. Ghosh, A. Gupta, T. Herman and S. Pemmaraju: Fault-containing self-stabilizing algorithms. Proc. 15th Ann. ACM Symp. on Principles of Dist. Comp. 1996, 45-54.
• [9] W. Goddard, S. T. Hedetniemi, D. Pokrass Jacobs and P. K. Srimani: Fault tolerant algorithms for orderings and colorings. IPDPS, 2004.
• [10] D. Grabie and A. .Panconesi: Nearly optimal distributed edge colouring in O(loglogn) rounds. Random Structures and Algorithms 10, 1997, 385-405.
• [11] S. T. Hedetniemi, D. P. Jacobs, and P. K. Srimani: Linear time self-stabilizing colorings. Inform. Process. Lett. 87, 2003, 251-255.
• [12] J.-H. Hoepman: Self-stabilizing ring orientation nsing constant space. Inform, and Comput. 144, 1998, 18-39.
• [13] I. Holyer: The NP-completeness of edge-coloring. SIAM J. Comput. 10, 1981, 718-720.
• [14] S. C. Hsu and S. T. Huang: A self-stabilizing algorithm for maximal matching. Inform. Process. Lett. 43, 1992, 77-81.
• [15] M. Kubale: Introduction to Computational Complexity and Algorithmic Graph Coloring. GTN, Gdańsk, 1998.
• [16] M. V. Marathe, A. Panconesi, and L. D. Risinger: An experimental study of a simple, distributed edge coloring algorithm. Proceedings of the twelfth annual ACM symposium on Parallel Algorithms and Architectures. ACM Press, 2000, 166-175.
• [17] T. Masuzawa and S. Tixeuil: A self-stabilizing link-coloring protocol resilient to unbounded byzantine faults in arbitrary networks. Technical Report 1396, Labora-toire de Recherche en Informatique, 2005.
• [18] A. Panconesi and R. Rizzi: Some simple distributed algorithms for sparse networks. Distributed Computing 14, 2001, 97-100.
• [19] A. Panconesi and A. Srimvasan: Randomized Distributed Edge Coloring via an Extension of the Chernoff-Hoeffding Bounds. SIAM J. Comput. 26, 1997, 350-368.
• [20] S. Sur and P. K. Srimani: A self-stabilizing algorithm for coloring bipartite graphs. Inform. Sci. 69, 1993, 219-227.
• [21] V. G. Vizing: On an estimate of the chromatic class of a p-graph Diskret Analiz 3, 1964, 25-30.