Repozytorium publikacji - Politechnika Gdańska

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.

Autorzy

• dr hab. inż. Robert Janczewski link otwiera się w nowej karcie ,
• dr inż. Krzysztof Turowski link otwiera się w nowej karcie