Wyniki wyszukiwania - Biblioteka Nauki

1

Algorytmiczne oszacowania liczby chromatycznej grafu

100%

Borowiecki P.

|

2008

|

tom T. 15

159-164

PL

Liczba chromatyczna grafu jest najmniejszą liczbą kolorów niezbędnych do pokolorowania jego wierzchołków w taki sposób, aby żadne dwa sąsiednie wierzchołki nie miały tego samego koloru. W ogólnym przypadku problem wyznaczenia liczby chromatycznej jest problemem NP-trudnym, stąd duże zainteresowanie parametrami graf owym i, które można wykorzystać do opisu oszacowań wartości liczby chromatycznej. W pracy tej omawiamy własności parametrów wywodzących się z pojęcia funkcji potencjału grafu oraz badamy ich powiązania z klasycznymi parametrami takimi jak liczba Welsha-Powella oraz liczba Szekeresa-Wilfa. Przedstawiamy także wyniki eksperymentalnego porównania dwóch znanych algorytmów sekwencyjnych z algorytmami porządkującymi wierzchołki według wartości funkcji potencjału.

EN

The chromatic number of a graph is the smallest number of colors required to color its vertices such that no two adjacent vertices share a color. In the general case determining the chromatic number of a graph is NP-hard, thus any graph invariants useful in bounding it are of great interest. Within this paper we discuss the properties of the invariants originating in the notion of a potential function. We study their interdependencies and the relationships to the classical Welsh-Powell and Szekeres- Wilf numbers. We also present the results of experimental comparison of two known sequential algorithms to the algorithms that use orderings of vertices with respect to their potentials.

2

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

100%

Borowiecki P.

|

2002

|

tom z. 136

11-20

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śród parametrów pozwalających na ocenę oczekiwanego zachowania algorytmu kolorowania w trybie on-line koncentrujemy się na podatności grafu. Definiujemy operację zachowującą podatność dla algorytmu First-Fit. Dla tego samego algorytmu rozstrzygamy również problem istnienia grafów o dowolnie małej podatności. Dla znanej z wielu zastosowań rodziny grafów przedziałów prezentowane są wnioski płynące z eksperymentalnego porównania efektywności dwóch znanych algorytmów kolorowania on-line.

EN

It usually happens that worst case analysis leads to the results which are too pessimistic to be valuable in real live applications. In this paper we investigate an expected effectiveness of on-line graph coloring algorithms, in particular the susceptibility of graphs to algorithm First-Fit is analyzed. The operation preserving susceptibilty is defined and an existence of graphs having arbitrarily low susceptibility to First-Fit, is proved. For well known and widely applicable family of interval graphs, the results of comparative experimental study of expected behavior for two on-line coloring algorithms are given.

3

Kolorowanie grafów w trybie on-line

100%

Borowiecki P.

|

1998

|

tom z. 123

65-75

PL

Natura wielu rzeczywistych problemów powoduje, że muszą być one rozwiązywane przy użyciu algorytmów działających w trybie on-line. Algorytm rozwiązujący taki problem w trybie off-line ma wtedy poważnie ograniczoną przydatność praktyczną. Niniejsza praca poświęcona jest problemowi kolorowania grafów w trybie on-line. Przedstawione są najważniejsze wyniki dotyczące tego problemu, w tym przegląd oszacowań liczby on-line chromatycznej, przykłady zastosowań oraz opis podstawowych algorytmów kolorowania grafów w trybie on-line.

EN

It is an inherent character of many problems, that they have to be solved on-line. Any off-line algorithm has a limited power to solve such problems in practice. In this paper we investigate the problem of on-line graph coloring. We review most important results and bounds on the on-line chromatic number. An application examples and description of basic on-line algorithms for graph coloring are included.

4

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

100%

Borowiecki P.

|

2000

|

tom z. 131

11-23

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.

5

Dynamic Coloring of Graphs

63%

Borowiecki P. , Sidorowicz E.

|

2012

|

tom Vol. 114, nr 2

105-128

EN

Dynamics is an inherent feature of many real life systems so it is natural to define and investigate the properties of models that reflect their dynamic nature. Dynamic graph colorings can be naturally applied in system modeling, e.g. for scheduling threads of parallel programs, time sharing in wireless networks, session scheduling in high-speed LAN’s, channel assignment inWDM optical networks as well as traffic scheduling. In the dynamic setting of the problem, a graph we color is not given in advance and new vertices together with adjacent edges are revealed one after another at algorithm’s input during the coloring process. Moreover, independently of the algorithm, some vertices may lose their colors and the algorithm may be asked to color them again. We formally define a dynamic graph coloring problem, the dynamic chromatic number and prove various bounds on its value. We also analyze the effectiveness of the dynamic coloring algorithm Dynamic-Fit for selected classes of graphs. In particular, we deal with trees, products of graphs and classes of graphs for which Dynamic-Fit is competitive. Motivated by applications, we state the problemof dynamic coloringwith discoloring constraints for which the performance of the dynamic algorithmTime-Fit is analyzed and give a characterization of graphs k-critical for Time-Fit. Since for any fixed k > 0 the number of such graphs is finite, it is possible to decide in polynomial time whether Time-Fit will always color a given graph with at most k colors.

6

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

63%

Borowiecki P. , Sidorowicz E.

|

2006

|

tom z. 144

135-142

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.