Uporządkowane kolorowane wierzchołki grafów

• Autorzy: Kubale M. , Dereniowski D.

Warianty tytułu

EN

Ordered coloring of graph vertices

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

Abstrakty

PL

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.

EN

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.

Słowa kluczowe

PL

grafy; kolorowanie grafów; kolorowanie uporządkowane

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

Twórcy

autor

Kubale M.

autor

Dereniowski D.

• Politechnika Gdańska, Gdańsk