Wyniki wyszukiwania dla: DRZEWO WIELOKĄTOWE

• Equitable 4-coloring of cacti and edge-cacti in polynomial time

  Publikacja

  • H. Furmańczyk
  • K. Giaro
  • M. Kubale

  - International Journal of Pure and Applied Mathematics - Rok 2006

  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.

  Pełny tekst do pobrania w serwisie zewnętrznym