Abstract
Artykuł traktuje o zachłannym kolorowaniu grafów w modelu rozproszonym. Zaprezentowano nowy probabilistyczny algorytm dający w wyniku pokolorowanie LF. Udowodniono, że jakakolwiek rozproszona implementacja LF wymaga co najmniej D rund, gdzie D jest maksymalnym stopniem wierzchołka w grafie.
Citations
-
9
CrossRef
-
0
Web of Science
-
1 0
Scopus
Authors (2)
Cite as
Full text
full text is not available in portal
Keywords
Details
- Category:
- Conference activity
- Type:
- publikacja w wydawnictwie zbiorowym recenzowanym (także w materiałach konferencyjnych)
- Title of issue:
- Euro-Par 2006 Parallel Processing : 12th International Euro-Par Conference, Dresden, Germany, August 28 - September 1, 2006 strony 592 - 601
- Language:
- English
- Publication year:
- 2006
- Bibliographic description:
- Kosowski A., Kuszner Ł.: On greedy graph coloring in the distributed model// Euro-Par 2006 Parallel Processing : 12th International Euro-Par Conference, Dresden, Germany, August 28 - September 1, 2006/ ed. eds: W.E. Nagel, W.V. Walter, W. Lehner. Berlin: Springer-Verlag, 2006, s.592-601
- DOI:
- Digital Object Identifier (open in new tab) 10.1007/11823285_61
- Verified by:
- Gdańsk University of Technology
seen 80 times
Recommended for you
On the complexity of distributed graph coloring with local minimality constraints
- C. Gavoille,
- R. Klasing,
- A. Kosowski
- + 2 authors
2009