Search results for: KOLOROWANIE SPRAWIEDLIWE

• Sprawiedliwe kolorowanie grafów

  Publication

  • H. Furmańczyk

  - Year 2002

  Kolorowanie sprawiedliwe jest kolorowaniem klasycznym z dodatkowym ograni-czeniem: chcemy, aby krotności użycia kolorów różniły się co najwyżej o je-den. W pracy przedstawiamy wyniki dotyczące sprawiedliwego kolorowania wie-rzchołków, krawędzi oraz obu tych elementów jednocześnie. Ponieważ problemjest NP-zupełny w ogólnym przypadku, poszukuje się algorytmów przybliżonych.Przedstawiamy dwa takie algorytmy.

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

  Publication

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

  - International Journal of Pure and Applied Mathematics - Year 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.

  Full text to download in external service

• Sprawiedliwe i półsprawiedliwe pokolorowania grafów kubicznych

  Publication

  • H. Furmańczyk
  • M. Kubale

  - Year 2014

  W pracy rozpatrywane są sprawiedliwe i półsprawiedliwe pokolorowania grafów kubicznych. Pokazano, że w odróżnieniu od tego pierwszego, który jest łatwy, problem istnienia pokolorowań półsprawiedliwych jest NP-zupełny w szerokim zakresie parametrów grafów.