Wyniki wyszukiwania - BazTech

Ograniczanie wyników

Znaleziono wyników: 1

Liczba wyników na stronie

Wyniki wyszukiwania

Wyszukiwano:
w słowach kluczowych: grafy niepodatne

Sortuj według:

Ogranicz wyniki do:

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

Borowiecki P.

Zeszyty Naukowe. Automatyka / Politechnika Śląska

2000

z. 131

11-23

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 niniejszej pracy rozważamy parametry, które pozwalają na ocenę oczekiwanego zachowania algorytmów kolorowania wierzchołków grafów w trybie on-line. W szczególności koncentrujemy się na oszacowaniach przeciętnej liczby chromatycznej, przeciętnej dobroci, funkcji przeciętnej dobroci i nowo zdefiniowanej podatności grafu dla algorytmu A. Podajemy rezultaty teoretyczne oraz wyniki eksperymentów obliczeniowych przeprowadzonych dla algorytmu First-Fit.

It usually happens that worst case analysis leads to the results which are too pessimistic to be valuable in real life applications. In this paper we investigate an expected effectiveness of on-line graph coloring algorithms. The mean chromatic number, mean performance ratio and mean performance function as well as newly denned susceptibility of graph to algorithm A are analyzed. Experimental results for algorithm First-Fit are presented, too.