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

• Autorzy: Borowiecki P.

Warianty tytułu

EN

Effectiveness of on0line graph coloring algorithms

• Konferencja: Automatyzacja procesów dyskretnych/krajowa konferencja (XII ; 13-16.09.2000 ; Zakopane)
• 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 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.

EN

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.

Słowa kluczowe

PL

kolorowanie grafów; kolorowanie on-line; grafy niepodatne

• Wydawca: Wydawnictwo Politechniki Śląskiej
• Czasopismo: Zeszyty Naukowe. Automatyka / Politechnika Śląska
• Rocznik: 2000
• Tom: z. 131
• Strony: 11--23
• Opis fizyczny: Bibliogr. 16 poz.

Twórcy

autor

Borowiecki P.

• Politechnika Zielonogórska