Distributed largest-first algorithm for graph coloring.

Łukasz Kuszner; Adam Nadolski; Marek Kubale; Jennie Hansen

Distributed largest-first algorithm for graph coloring.

Abstract

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 (4)

Łukasz Kuszner dr inż.
- Faculty of Electronics, Telecommunications and Informatics
- Gdańsk University of Technology
Adam Nadolski dr inż.
- Faculty of Electronics, Telecommunications and Informatics
- Gdańsk University of Technology
Marek Kubale prof. dr hab. inż.
- Faculty of Electronics, Telecommunications and Informatics
- Gdańsk University of Technology
Jennie Hansen
- Faculty of Electronics, Telecommunications and Informatics
- Gdańsk University of Technology

Cite as

Full text

full text is not available in portal

Keywords

Details

Category:: Articles
Type:: artykuł w czasopiśmie z listy filadelfijskiej
Language:: English
Publication year:: 2004
Bibliographic description:: Kuszner Ł., Nadolski A., Kubale M., Hansen J.: Distributed largest-first algorithm for graph coloring.// . -., (2004),
Verified by:: Gdańsk University of Technology