Wyniki wyszukiwania - BazTech

Ograniczanie wyników

Znaleziono wyników: 1

Liczba wyników na stronie

Wyniki wyszukiwania

Wyszukiwano:
w słowach kluczowych: algorytm First-Fit

Sortuj według:

Ogranicz wyniki do:

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

Borowiecki P.

Zeszyty Naukowe. Automatyka / Politechnika Śląska

2002

z. 136

11-20

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.