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 kolorowania nieparzystych cykli, wraz z dowodem NP-zupełności tego problemu. Jeśli nieparzysty cykl posiada dołączoną ścieżkę długości dwa, to problem stwierdzenia istnienia zwartego cyrkularnego pokolorowania staje się NP-zupełny.
Autorzy
Informacje dodatkowe
- Kategoria
- Publikacja w czasopiśmie
- Typ
- artykuł w czasopiśmie z listy filadelfijskiej
- Język
- angielski
- Rok wydania
- 2008
Źródło danych: MOSTWiedzy.pl - publikacja "A note on compact and compact circular edge-colorings of graphs" link otwiera się w nowej karcie
