Wyniki wyszukiwania - BazTech

Ograniczanie wyników

Znaleziono wyników: 1

Liczba wyników na stronie

Wyniki wyszukiwania

Sortuj według:

Ogranicz wyniki do:

Algorytmy sprawiedliwego kolorowania grafów

Damrath H.

Zeszyty Naukowe. Automatyka / Politechnika Śląska

1998

z. 123

111-120

Problemy kolorowania grafów należą do najtrudniejszych problemów optymalizacji kombinatorycznej z punktu widzenia złożoności obliczeniowej. W niniejszej pracy rozważono zagadnienie sprawiedliwego kolorowania wierzchołków grafu, tj. takiego kolorowania, że krotności użycia dowolnych kolorów różnią się najwyżej o 1. Pokazano, że problem ten jest NP-trudny i sformułowano dwa algorytmy heurystyczne dla usprawiedliwienia rozwiązań uzyskanych innymi algorytmami kolorowania. Podano doświadczenia komputerowe z implementacji i testowania tych algorytmów na identycznych seriach grafów pseudolosowych.

Graph coloring problems belong to the hardest combinatorial optimization problems with respect to the computational complexity. In this paper we consider the problem of equitable coloring the vertices of a graph, i.e. such a coloring that the sizes of color classes differ by at most 1. We show that the problem is NP-hard and give two heuristic algorithms for tranforming colorings obtained by other standard algorithms into equitable solutions. General considerations are supported by computational experience gained with implementation and profiling of these algorithms on identical series of pseudorandom graphs.