Wyszukiwarka
Abstrakt
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.
Cytowania
-
1 8
CrossRef
-
0
Web of Science
-
2 2
Scopus
Autorzy (5)
Cytuj jako
Pełna treść
pobierz publikację
pobrano 6 razy
- Wersja publikacji
- Accepted albo Published Version
- DOI:
- Cyfrowy identyfikator dokumentu elektronicznego (otwiera się w nowej karcie) 10.1002/net.20293
- Licencja
- Copyright (2009 Wiley Periodicals, Inc.)
Słowa kluczowe
Informacje szczegółowe
- Kategoria:
- Publikacja w czasopiśmie
- Typ:
- artykuł w czasopiśmie wyróżnionym w JCR
- Opublikowano w:
-
NETWORKS
nr 54,
strony 12 - 19,
ISSN: 0028-3045 - Język:
- angielski
- Rok wydania:
- 2009
- Opis bibliograficzny:
- 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:
- Cyfrowy identyfikator dokumentu elektronicznego (otwiera się w nowej karcie) 10.1002/net.20293
- Weryfikacja:
- Politechnika Gdańska
wyświetlono 116 razy