Tytuł artykułu
Autorzy
Identyfikatory
Warianty tytułu
Effectiveness of on-line graph coloring algorithms (II)
Konferencja
XIII Krajowa Konferencja Automatyzacji Procesów Dyskretnych
Języki publikacji
Abstrakty
Z praktycznego punktu widzenia analiza najgorszego przypadku okazuje się często zbyt pesymistyczna, natomiast zachowanie algorytmu dla spotykanych w rzeczywistości danych jest najczęściej dużo lepsze niż dla stosunkowo nielicznych instancji, decydujących o złej efektywności w najgorszym przypadku. Wśród parametrów pozwalających na ocenę oczekiwanego zachowania algorytmu kolorowania w trybie on-line koncentrujemy się na podatności grafu. Definiujemy operację zachowującą podatność dla algorytmu First-Fit. Dla tego samego algorytmu rozstrzygamy również problem istnienia grafów o dowolnie małej podatności. Dla znanej z wielu zastosowań rodziny grafów przedziałów prezentowane są wnioski płynące z eksperymentalnego porównania efektywności dwóch znanych algorytmów kolorowania on-line.
It usually happens that worst case analysis leads to the results which are too pessimistic to be valuable in real live applications. In this paper we investigate an expected effectiveness of on-line graph coloring algorithms, in particular the susceptibility of graphs to algorithm First-Fit is analyzed. The operation preserving susceptibilty is defined and an existence of graphs having arbitrarily low susceptibility to First-Fit, is proved. For well known and widely applicable family of interval graphs, the results of comparative experimental study of expected behavior for two on-line coloring algorithms are given.
Słowa kluczowe
Rocznik
Tom
Strony
11--20
Opis fizyczny
Bibliogr. 9 poz.
Twórcy
autor
- Uniwersytet Zielonogórski, Zielona Góra
Bibliografia
Typ dokumentu
Bibliografia
Identyfikator YADDA
bwmeta1.element.baztech-article-BSL6-0008-0032