Wyszukiwarka
Abstrakt
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.
Cytuj jako
Pełna treść
pełna treść publikacji nie jest dostępna w portalu
Słowa kluczowe
Informacje szczegółowe
- Kategoria:
- Publikacja w czasopiśmie
- Typ:
- artykuł w czasopiśmie z listy filadelfijskiej
- Język:
- angielski
- Rok wydania:
- 2004
- Opis bibliograficzny:
- Kuszner Ł., Nadolski A., Kubale M., Hansen J.: Distributed largest-first algorithm for graph coloring.// . -., (2004),
- Weryfikacja:
- Politechnika Gdańska
wyświetlono 314 razy
Publikacje, które mogą cię zainteresować
On the complexity of distributed graph coloring with local minimality constraints
- C. Gavoille,
- R. Klasing,
- A. Kosowski
- + 2 autorów
2009