Wyszukiwarka
Abstrakt
Rozważono problem wyznaczania sprawiedliwej liczby chromatycznej kaktusów i drzew wielokątowych bez trójkątów i krawędzi wiszących. Podano wielomianowy algorytm wyznaczający pokolorowanie optymalne, oparty na paradygmacie programowania dynamicznego. Tym samym znaleziona została kolejna klasa grafów planarnych, dla której kolorowanie sprawiedliwe jawi się jako zagadnienie obliczeniowo łatwe.
Autorzy (3)
Cytuj jako
Pełna treść
pełna treść publikacji nie jest dostępna w portalu
Słowa kluczowe
Informacje szczegółowe
- Kategoria:
- Publikacja w czasopiśmie
- Typ:
- artykuły w czasopismach recenzowanych i innych wydawnictwach ciągłych
- Opublikowano w:
-
International Journal of Pure and Applied Mathematics
nr 27,
strony 377 - 389,
ISSN: 1311-8080 - Język:
- angielski
- Rok wydania:
- 2006
- Opis bibliograficzny:
- Furmańczyk H., Giaro K., Kubale M.: Equitable 4-coloring of cacti and edge-cacti in polynomial time// International Journal of Pure and Applied Mathematics. -Vol. 27., iss. 3 (2006), s.377-389
- Weryfikacja:
- Politechnika Gdańska
wyświetlono 128 razy