Efektywność algorytmów kolorowania grafów w trybie on-line (II)

• Autorzy: Borowiecki P.

Warianty tytułu

EN

Effectiveness of on-line graph coloring algorithms (II)

• Konferencja: XIII Krajowa Konferencja Automatyzacji Procesów Dyskretnych
• Języki publikacji: PL

Abstrakty

PL

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.

EN

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

PL

grafy; kolorowanie grafów; algorytm First-Fit

• Wydawca: Wydawnictwo Politechniki Śląskiej
• Czasopismo: Zeszyty Naukowe. Automatyka / Politechnika Śląska
• Rocznik: 2002
• Tom: z. 136
• Strony: 11--20
• Opis fizyczny: Bibliogr. 9 poz.

Twórcy

autor

Borowiecki P.

• Uniwersytet Zielonogórski, Zielona Góra