Problem harmonicznego kolorowania wierzchołków grafu

• Autorzy: Kubale M.

Warianty tytułu

EN

Problem of harmonious coloring of graph vertices

• Konferencja: Automatyzacja procesów dyskretnych/krajowa konferencja (XII ; 13-16.09.2000 ; Zakopane)
• Języki publikacji: PL

Abstrakty

PL

Kolorowanie harmoniczne wierzchołków grafu jest taką odmianą kolorowania klasycznego, która ma oryginalne zastosowania praktyczne. W niniejszej pracy pokazujemy, że problem kolorowania harmonicznego jest NP-trudny, podajemy najważniejsze wyniki teoretyczne dotyczące harmonicznej liczby chromatycznej i proponujemy algorytm heurystyczny dla takiego kolorowania. Algorytm ten jest 2-przybliżony, ma złożoność 0(n4) i działa skutecznie na grafach losowych.

EN

Harmonious coloring the vertices of a graph is such a variation of classical model of coloring which has extraordinary applications. In the paper we show that the problem of harmonious coloring is NP-hard, give the main theoretical results for harmonious chromatic number and propose a heuristic algorithm for such a coloring. This algorithm is 2-approximate, runs in 0(n4) time and behaves effectively on random graphs.

Słowa kluczowe

PL

kolorowanie grafów; algorytm heurystyczny

• Wydawca: Wydawnictwo Politechniki Śląskiej
• Czasopismo: Zeszyty Naukowe. Automatyka / Politechnika Śląska
• Rocznik: 2000
• Tom: z. 131
• Strony: 103--110
• Opis fizyczny: Bibliogr. 12 poz.

Twórcy

autor

Kubale M.

• Katedra Podstaw Informatyki Politechnika Gdańska, 80-952 Gdańsk, ul. Narutowicza 11/12, tel. [phone],