W artykule zaprezentowano rozproszony, probabilistyczny algorytm kolorowania grafów. Kolorowanie uzyskane jest optymalne lub prawie optymalne dla takich klas grafów jak koła dwudzielne, gąsienice czy korony. Udowodniono, że algorytm ten działa w czasie O(D^2 log n) rund dla dowolnego grafu n wierzchołkowegoo stopniu maksymalnym D.
Authors
Additional information
- Category
- Publikacja w czasopiśmie
- Type
- artykuł w czasopiśmie z listy filadelfijskiej
- Language
- angielski
- Publication year
- 2004
