An $$O(n\log n)$$ O ( n log n ) algorithm for finding edge span of cacti
Robert Janczewski, Krzysztof Turowski · Journal of Combinatorial Optimization · 2015
Let $$G=(V,E)$$ be a nonempty graph and $$\xi :E\rightarrow \mathbb {N}$$ be a function. In the paper we study the computational complexity of the problem of finding vertex colorings $$c$$ of $$G$$ such that: 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(n\log n)$$ time, where $$n$$ is the number of vertices of $$G$$ .