Wyszukiwarka
The computational complexity of the backbone coloring problem for planar graphs with connected backbones
Abstrakt
In the paper we study the computational complexity of the backbone coloring problem for planar graphs with connected backbones. For every possible value of integer parameters λ≥2 and k≥1 we show that the following problem: Instance: A simple planar graph GG, its connected spanning subgraph (backbone) HH. Question: Is there a λ-backbone coloring c of G with backbone H such that maxc(V(G))≤k? is either NP-complete or polynomially solvable (by algorithms that run in constant, linear or quadratic time). As a result of these considerations we obtain a complete classification of the computational complexity with respect to the values of λ and k. We also study the problem of computing the backbone chromatic number for two special classes of planar graphs: cacti and thorny graphs. We construct an algorithm that runs in O(n^3) time and solves this problem for cacti and another polynomial algorithm that is 1-absolute approximate for thorny graphs.
Cytowania
-
1
CrossRef
-
0
Web of Science
-
1
Scopus
Cytuj jako
Pełna treść
- Wersja publikacji
- Accepted albo Published Version
- DOI:
- Cyfrowy identyfikator dokumentu elektronicznego (otwiera się w nowej karcie) 10.1016/j.dam.2014.10.028
- Licencja
- Copyright (2014 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 APPLIED MATHEMATICS
nr 184,
strony 237 - 242,
ISSN: 0166-218X - Język:
- angielski
- Rok wydania:
- 2015
- Opis bibliograficzny:
- Janczewski R., Turowski K.: The computational complexity of the backbone coloring problem for planar graphs with connected backbones// DISCRETE APPLIED MATHEMATICS. -Vol. 184, (2015), s.237-242
- DOI:
- Cyfrowy identyfikator dokumentu elektronicznego (otwiera się w nowej karcie) 10.1016/j.dam.2014.10.028
- Weryfikacja:
- Politechnika Gdańska
wyświetlono 137 razy