Efficient list cost coloring of vertices and/or edges of bounded cyclicity graphs

Krzysztof Giaro; Marek Kubale

Efficient list cost coloring of vertices and/or edges of bounded cyclicity graphs

Abstract

W artykule rozważamy listowo-kosztowe kolorowanie wierzchołków i krawędzi grafu w modelu wierzchołkowym, krawędziowym, totalnym i pseudototalnym. Stosujemy programowanie dynamiczne w celu otrzymania algorytmów wielomianowych dla drzew. Następnie uogólniamy to podejście na dowolne grafy z ograniczonymi liczbami cyklomatycznymi i na ich multikolorowania.

Authors (2)

Krzysztof Giaro prof. dr hab. inż.
Marek Kubale prof. dr hab. inż.

Cite as

Full text

download paper

downloaded 36 times

Publication version: Accepted or Published Version
License: open in new tab

full content of the article see on external site open in new tab

Keywords

Details

Category:: Articles
Type:: artykuły w czasopismach recenzowanych i innych wydawnictwach ciągłych
Published in:: Discussiones Mathematicae Graph Theory no. 29, pages 361 - 376,
ISSN: 1234-3099
Language:: English
Publication year:: 2009
Bibliographic description:: Giaro K., Kubale M.: Efficient list cost coloring of vertices and/or edges of bounded cyclicity graphs// Discussiones Mathematicae Graph Theory. -Vol. 29., iss. No. 2 (2009), s.361-376
Verified by:: Gdańsk University of Technology