Wyszukiwarka
Abstrakt
W pracy pokazano, że problem L(p,q)-kolorowania przy użyciu ''t'' kolorów jest NP-zupełny nawet w wersji ograniczonej do grafów planarnych dwudzielnych małego stopnia, nawet dla stosunkowo niewielkich wartości ''t''. Jako wniosek z uzyskanych wyników stwierdzono, że problem L(2,1)-kolorowania grafów planarnych przy użyciu 4 kolorów jest NP-zupełny, a także że problem L(p,q)-kolorowania grafów o maksymalnym stopniu 4 jest NP-zupełny dla wszystkich wartości ''p'' i ''q'', zamykając tym samym dwa problemy otwarte stawiane w literaturze.
Cytowania
-
9
CrossRef
-
0
Web of Science
-
8
Scopus
Autorzy (3)
Cytuj jako
Pełna treść
pobierz publikację
pobrano 9 razy
- Wersja publikacji
- Accepted albo Published Version
- DOI:
- Cyfrowy identyfikator dokumentu elektronicznego (otwiera się w nowej karcie) 10.1016/j.disc.2008.09.028
- Licencja
- Copyright (2008 Elsevier B.V)
Słowa kluczowe
Informacje szczegółowe
- Kategoria:
- Publikacja w czasopiśmie
- Typ:
- artykuł w czasopiśmie wyróżnionym w JCR
- Opublikowano w:
-
DISCRETE MATHEMATICS
nr 309,
strony 3270 - 3279,
ISSN: 0012-365X - Język:
- angielski
- Rok wydania:
- 2009
- Opis bibliograficzny:
- Janczewski R., Kosowski A., Małafiejski M.: The complexity of the L(p,q)-labeling problem for bipartite planar graphs of small degree // DISCRETE MATHEMATICS. -Vol. 309, (2009), s.3270-3279
- DOI:
- Cyfrowy identyfikator dokumentu elektronicznego (otwiera się w nowej karcie) 10.1016/j.disc.2008.09.028
- Weryfikacja:
- Politechnika Gdańska
wyświetlono 148 razy