Wyniki wyszukiwania dla: KOLOROWANIE KOSZTOWE

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

  Publikacja

  • K. Giaro
  • M. Kubale

  - Discussiones Mathematicae Graph Theory - Rok 2009

  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.

  Pełny tekst do pobrania w portalu

• Efficient list cost coloring of vertices and/or edges of some sparse graphs

  Publikacja

  • K. Giaro
  • M. Kubale

  - Rok 2007

  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.