PL EN


Preferencje help
Widoczny [Schowaj] Abstrakt
Liczba wyników
2006 | Vol. 31, No. 2 | 158-167
Tytuł artykułu

A self-stabilizing algorithm for edge-coloring of graphs

Warianty tytułu
Języki publikacji
EN
Abstrakty
Wydawca

Rocznik
Strony
158-167
Opis fizyczny
Bibliogr. 21 poz.
Twórcy
autor
autor
  • Gdańsk University of Technology, Department of Algorithms and System Modeling, Narutowicza 11/12, 80-952 Gdańsk, Poland, kuszner@eti.pg.gda.pl
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.
Typ dokumentu
Bibliografia
Identyfikatory
Identyfikator YADDA
bwmeta1.element.baztech-article-BPP1-0064-0051
JavaScript jest wyłączony w Twojej przeglądarce internetowej. Włącz go, a następnie odśwież stronę, aby móc w pełni z niej korzystać.