Repozytorium publikacji - Politechnika Gdańska

Let G=(V,E) be a nonempty graph and xi be a function. In the paper we study the computational complexity of the problem of finding vertex colorings c of G such that: (1) |c(u)-c(v)|>=xi(uv) for each edge uv of E; (2) the edge span of c, i.e. max{|c(u)-c(v)|: uv belongs to E}, is minimal. We show that the problem is NP-hard for subcubic outerplanar graphs of a very simple structure (similar to cycles) and polynomially solvable for cycles and bipartite graphs. Next, we use the last two results to construct an algorithm that solves the problem for a given cactus G in O(nlog n) time, where n is the number of vertices of G.

Autorzy

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