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.
Authors
- Cyril Gavoille,
- Ralf Klasing,
- dr inż. Adrian Kosowski link open in new tab ,
- dr inż. Łukasz Kuszner link open in new tab ,
- Alfredo Navarra
Additional information
- DOI
- Digital Object Identifier link open in new tab 10.1002/net.20293
- Category
- Publikacja w czasopiśmie
- Type
- artykuł w czasopiśmie wyróżnionym w JCR
- Language
- angielski
- Publication year
- 2009
