Warianty tytułu
Effectiveness of dynamic graph coloring algorithms - applications to WDM optical networks
Konferencja
XV Krajowa Konferencja Automatyzacji Procesów Dyskretnych, Zakopane, 20-23 września 2006r.
Języki publikacji
Abstrakty
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.
Rocznik
Tom
Strony
135-142
Opis fizyczny
Bibliogr. 4 poz.
Twórcy
autor
autor
- Zakład Matematyki Dyskretnej, Algebry i Informatyki, Wydział Matematyki, Informatyki i Ekonometrii Uniwersytetu Zielonogórskiego, 65-516 Zielona Góra, ul. prof. Z. Szafrana 4a, tel. (068) 328-28-69, P.Borowiecki@wmie.uz.zgora.pl
Bibliografia
- 1. Borowiecki P.: Kolorowanie w trybie on-line. W: M. Kubale red., Optymalizacja dyskretna. Modele i metody kolorowania grafów, WNT, Warszawa 2002, s. 53-71.
- 2. Gyárfás A., Leliel J.: First-Fit and on-line chromatic number of families of graphs. Ars Combinatoria 29C, 1990, p. 168-176.
- 3. McDiarmid C.J.H.: Coloring random graphs badly. W: R.J. Wilson red., Graph Theory and Combinatorics, Pitman, 1979, p. 76-86.
- 4. Pemmaraju S.V., Raman R., Varadarajan K.: Buffer minimization using max-coloring, Proc. 15th ACM-SIAM Symposium on Discrete Algorithms, 2004.
Typ dokumentu
Bibliografia
Identyfikatory
Identyfikator YADDA
bwmeta1.element.baztech-article-BSL2-0013-0015