Wyniki wyszukiwania dla: CYRKULARNE POKOLOROWANIE

• A note on compact and compact circular edge-colorings of graphs

  Publikacja

  • D. Dereniowski
  • A. Nadolski

  - DISCRETE MATHEMATICS - Rok 2008

  W pracy rozważamy dwa warianty kolorowania krawędzi grafów prostych i ważonych, mianowicie kolorowania zwarte oraz zwarte cyrkularne. Rozważamy relacje pomiędzy nimi. Dowodzimy, że każdy zewnętrznie planarny graf dwudzielny posiada zwarte pokolorowanie krawędziowe oraz, że problem ten dla grafów ogólnych jest NP-zupełny. Podajemy również wielomianowy 1.5-przybliżony algorytm oraz pseudowielomianowy dokładny algorytm zwartego cyrkularnego...

  Pełny tekst do pobrania w serwisie zewnętrznym

• Algorytm przybliżony dla cyrkularnego kolorowania krawędzi grafów

  Publikacja

  • R. Janczewski
  • Ł. Kuszner
  • M. Małafiejski
  • A. Nadolski

  - Zeszyty Naukowe Wydziału ETI Politechniki Gdańskiej. Technologie Informacyjne - Rok 2003

  W artykule autorzy proponują algorytm przybliżony dla cylkularnego kolorowania krawędzi grafu. Przedstawione są oszacowania na złożoność obliczeniową tego algorytmu, a także wyniki testów na grafach o małej liczbie wierzchołków jak i na grafach losowych.