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

• Autorzy: Borowiecki P. , Sidorowicz E.

Warianty tytułu

EN

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: PL

Abstrakty

PL

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).

EN

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.

Słowa kluczowe

PL

graf; kolorowanie grafów; kolorowanie dynamiczne; sieć optyczna; sieć WDM; algorytm zachłanny

EN

graph; graph coloring; dynamic coloring; optical network; WDM network; First-Fit algorithm

• Wydawca: Wydawnictwo Politechniki Śląskiej
• Czasopismo: Zeszyty Naukowe. Automatyka / Politechnika Śląska
• Rocznik: 2006
• Tom: z. 144
• Strony: 135--142
• Opis fizyczny: Bibliogr. 4 poz.

Twórcy

autor

Borowiecki P.

autor

Sidorowicz E.

• 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. [phone],

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.