Search
Abstract
Artykuł traktuje o zachłannym kolorowaniu grafów w modelu rozproszonym. Omówiono algorytmy rozproszone, dające w wyniku pokolorowanie spełniające warunki dla pokolorowań sekwencyjnych typu S oraz Largest-First (LF). Udowodniono również, że każda rozproszona implementacja algorytmu S wymaga co najmniej Omega(log n / log log n) rund, a algorytmu LF co najmniej Omega (n^{1/2}) rund, gdzie n oznacza liczbę wierzchołków grafu.
Citations
-
1 8
CrossRef
-
0
Web of Science
-
2 2
Scopus
Authors (5)
Cite as
Full text
download paper
downloaded 9 times
- Publication version
- Accepted or Published Version
- DOI:
- Digital Object Identifier (open in new tab) 10.1002/net.20293
- License
- Copyright (2009 Wiley Periodicals, Inc.)
Keywords
Details
- Category:
- Articles
- Type:
- artykuł w czasopiśmie wyróżnionym w JCR
- Published in:
-
NETWORKS
no. 54,
pages 12 - 19,
ISSN: 0028-3045 - Language:
- English
- Publication year:
- 2009
- Bibliographic description:
- Gavoille C., Klasing R., Kosowski A., Kuszner Ł., Navarra A.: On the complexity of distributed graph coloring with local minimality constraints// NETWORKS. -Vol. 54, nr. iss. 1 (2009), s.12-19
- DOI:
- Digital Object Identifier (open in new tab) 10.1002/net.20293
- Verified by:
- Gdańsk University of Technology
seen 119 times