Algorytmy radiowego kolorowania grafów

• Autorzy: Kubale M. , Kosowski A.

Warianty tytułu

EN

Algorithms for radiocoloring of graphs

• Konferencja: XIII Krajowa Konferencja Automatyzacji Procesów Dyskretnych
• Języki publikacji: PL

Abstrakty

PL

W pracy opisane są podstawowe zasady i właściwości radiowego kolorowania grafów. Podane są oszacowania radiowej liczby chromatycznej grafu w przypadku ogólnym dla ścieżek i cykli oraz dokładne wartości radiowej liczby chromatycznej dla grafów pełnych k-dzielnych, kół i dwugwiazd. Zamieszczono także przykładowe wyniki porównania dobroci suboptymalnych, sekwencyjnych algorytmów radiokolorowania grafów.

EN

The basic principles and features of graph radiocoloring are presented in this paper. Lower and upper bounds for the radiochromatic number of graphs are given, in the general case as well as for paths and cycles. Exact values of the radiochromatic number are given for complete k-parite graphs, wheels and double stars. The paper also contains a comparison of the quality of suboptimal, sequential radiocoloring algorithms having polynomial-time complexity.

Słowa kluczowe

PL

kolorowanie grafów; kolorowanie radiowe; algorytm sekwencyjny

• Wydawca: Wydawnictwo Politechniki Śląskiej
• Czasopismo: Zeszyty Naukowe. Automatyka / Politechnika Śląska
• Rocznik: 2002
• Tom: z. 136
• Strony: 133--144
• Opis fizyczny: Bibliogr. 8 poz.

Twórcy

autor

Kubale M.

autor

Kosowski A.

• Politechnika Gdańska, Gdańsk