Search
Abstract
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.
Authors (2)
Cite as
Full text
full text is not available in portal
Keywords
Details
- Category:
- Articles
- Type:
- artykuł w czasopiśmie z listy filadelfijskiej
- Published in:
-
DISCRETE MATHEMATICS
no. 10,
pages 161 - 170,
ISSN: 0012-365X - Language:
- English
- Publication year:
- 2008
- Bibliographic description:
- 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
- Verified by:
- Gdańsk University of Technology
seen 92 times