Algorytmy sprawiedliwego kolorowania grafów

• Autorzy: Damrath H.

Warianty tytułu

EN

Algorithms for equitable graph coloring

• Konferencja: XI Krajowa Konferencja Automatyzacji Dyskretnych Procesów Przemysłowych, Zakopane, 24-27.09.1998
• Języki publikacji: PL

Abstrakty

PL

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.

EN

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.

Słowa kluczowe

PL

grafy; kolorowanie grafów; optymalizacja kombinatoryczna; problem NP-trudny

• Wydawca: Wydawnictwo Politechniki Śląskiej
• Czasopismo: Zeszyty Naukowe. Automatyka / Politechnika Śląska
• Rocznik: 1998
• Tom: z. 123
• Strony: 111--120
• Opis fizyczny: Bibliogr. 7 poz.

Twórcy

autor

Damrath H.

• Uniwersytet Gdański