Abstract
Rozważane jest kolorowanie wierzchołków i krawędzi grafów w modelach klasycznym, totalnym i pseudototalnym z uwzględnieniem dodatkowego ograniczenia w postaci list dostępnych kolorów. Proponujemy wielomianowy algorytm oparty na paradygmacie programowania dynamicznego dla grafów o strukturze drzewa. Wynik ten można uogólnić na grafy o liczbie cyklomatycznej ograniczonej z góry przez dowolnie wybraną stała.
Authors (2)
Cite as
Full text
full text is not available in portal
Keywords
Details
- Category:
- Conference activity
- Type:
- publikacja w wydawnictwie zbiorowym recenzowanym (także w materiałach konferencyjnych)
- Title of issue:
- ICNAAM 2007 : International Conference on Numerical Analysis and Applied Mathematics : Conference Proceedings, Corfu, Greece, 16-20 September 2007 strony 241 - 243
- Language:
- English
- Publication year:
- 2007
- Bibliographic description:
- Giaro K., Kubale M.: Efficient list cost coloring of vertices and/or edges of some sparse graphs// ICNAAM 2007 : International Conference on Numerical Analysis and Applied Mathematics : Conference Proceedings, Corfu, Greece, 16-20 September 2007/ ed. eds: T.E. Simos, G.P. Psihoylos, Ch. Tsitouras. Meliville: AIP, 2007, s.241-243
- Verified by:
- Gdańsk University of Technology
seen 84 times