On cycle covers of graphs with bounded pathwidth

V. V. Lepin

Institute of Mathematics of the National Academy of Sciences of Belarus

Abstract: In this paper we present space-efficient algorithms for solving construction variants of cycle cover problems on graphs with bounded pathwidth. Algorithms for solving the problem of finding a vertex disjoint cycle cover with minimal number of cycles and for solving the $\lambda$-cycle cover problem on this type of graphs in $O(n\log n)$ time with $O(1)$ additional memory are given.

UDC: 519.1

Received: 10.09.2010