Wyniki wyszukiwania - BazTech

Ograniczanie wyników

2 Zeszyty Naukowe. Automatyka / Politechnika Śląska

Znaleziono wyników: 2

Liczba wyników na stronie

Wyniki wyszukiwania

Wyszukiwano:
w słowach kluczowych: kolorowanie uporządkowane

Sortuj według:

Ogranicz wyniki do:

Generowanie sąsiedztwa w algorytmach lokalnych poszukiwań uporządkowanego kolorowania grafów

Dereniowski D.

Zeszyty Naukowe. Automatyka / Politechnika Śląska

2006

z. 143

51-56

Przedstawienie rozwiązań problemów kombinatorycznych w postaci permutacji daje podstawy do konstrukcji algorytmów lokalnych poszukiwań. Uporządkowane pokolorowanie grafu można zapisać w postaci permutacji wierzchołków grafu. Podstawowe operacje, prowadzące do generowania sąsiedztwa rozwiązania, to zamiana dwóch elementów lub przesunięcie elementu permutacji. W artykule wskazujemy metodę, pozwalającą na wykonanie takich operacji w czasie O(m), przy założeniu, że dane jest drzewo eliminacji wyjściowej permutacji.

Representing solutions to combinatorial problems as permutations allows us to use local search algorithms for solving them. A vertex ranking of a graph can be represented by a permutation of the vertices of the graph. Basic operations for generating a neighborhood of a current solution are swapping two elements of the permutation or changing a position of an element. We show how to perform such operations in time O(m) assuming that an elimination tree of the current permutation is given.

Uporządkowane kolorowane wierzchołki grafów

Kubale M., Dereniowski D.

Zeszyty Naukowe. Automatyka / Politechnika Śląska

2002

z. 136

121-131

W pracy przedstawiamy stosunkowo nowy model kolorowania grafów, mianowicie kolorowanie uporządkowane. Po scharakteryzowaniu potencjalnych zastosowań tego modelu przedstawiamy liniowy algorytm kolorowania grafów w sposób przybliżony. Pokazujemy klasy grafów, które ten algorytm koloruje optymalnie i klasy grafów, dla których błąd pokolorowania może być dowolnie duży. Przedstawiamy również doświadczenia komputerowe zebrane w trakcie jego implementacji i testowania na grafach losowych.

We present a relatively new model of graph coloring, namely ordered (rank) coloring. After characterizing potential applications of this model, we give a linear-time algorithm KU for approximate graph coloring. We show graph classes that our algorithm colors optimally and graph classes that can be colored arbitrarily bad. Finally, we give results of computational experiments gained while testing algorithm KU on random graphs.