Wyszukiwarka
Abstrakt
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 (2)
Cytuj jako
Pełna treść
pełna treść publikacji nie jest dostępna w portalu
Słowa kluczowe
Informacje szczegółowe
- Kategoria:
- Publikacja w czasopiśmie
- Typ:
- artykuł w czasopiśmie z listy filadelfijskiej
- Opublikowano w:
-
DISCRETE MATHEMATICS
nr 10,
strony 161 - 170,
ISSN: 0012-365X - Język:
- angielski
- Rok wydania:
- 2008
- Opis bibliograficzny:
- Dereniowski D., Nadolski A.: A note on compact and compact circular edge-colorings of graphs// DISCRETE MATHEMATICS. -Vol. 10., nr. nr 3 (2008), s.161-170
- Weryfikacja:
- Politechnika Gdańska
wyświetlono 92 razy