Wyniki wyszukiwania - BazTech

Ograniczanie wyników

1 Zeszyty Naukowe. Automatyka / Politechnika Śląska

1 2006

Znaleziono wyników: 1

Liczba wyników na stronie

Wyniki wyszukiwania

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

Sortuj według:

Ogranicz wyniki do:

Efektywność algorytmów dynamicznego kolorowania grafów - zastosowania w sieciach optycznych WDM

Borowiecki P., Sidorowicz E.

Zeszyty Naukowe. Automatyka / Politechnika Śląska

2006

z. 144

135-142

W pracy tej formułujemy problem dynamicznego kolorowania grafów, analizujemy efektywność algorytmu zachłannego First-Fit (w skrócie FF) oraz wskazujemy na jego zastosowanie w problemie przydziału długości fali w sieciach optycznych WDM. W szczególności podajemy dolne i górne oszacowania dobroci algorytmu FF. Wskazujemy istnienie klas grafów G, dla których różnica pomiędzy wartością rozwiązania generowanego przez algorytm FF(G) a wartością optymalną OPT(G) może być dowolnie duża. Z drugiej strony dowodzimy, że dla dowolnego grafu G używanego przez nas w problemie przydziału długości fali zawsze zachodzi FF(G) < 20PT(G).

Within this paper we introduce a problem of dynamie graph coloring and analyze effectiveness of greedy algorithm First-Fit (FF for short). We point out an important application of a new model to wavelength assignment problem in WDM networks. In particular, we give lower and upper bounds on the performance ratio of FF. We prove that for some classes of graphs G, the difference between the solution value FF(G) and optimum value OPT(G) may be arbitrarily large. On the other hand, for all graphs, that we used in the wavelength assignment problem FF(G) < 20PT(G) holds.