Abstrakt
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.
Autorzy (2)
Cytuj jako
Pełna treść
pełna treść publikacji nie jest dostępna w portalu
Słowa kluczowe
Informacje szczegółowe
- Kategoria:
- Aktywność konferencyjna
- Typ:
- publikacja w wydawnictwie zbiorowym recenzowanym (także w materiałach konferencyjnych)
- Tytuł wydania:
- ICNAAM 2007 : International Conference on Numerical Analysis and Applied Mathematics : Conference Proceedings, Corfu, Greece, 16-20 September 2007 strony 241 - 243
- Język:
- angielski
- Rok wydania:
- 2007
- Opis bibliograficzny:
- 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
- Weryfikacja:
- Politechnika Gdańska
wyświetlono 84 razy