This article is cited in 2 papers

Algorithms for solving problems on graphs of bounded pathwidth

V. V. Lepin

Institute of Mathematics of the National Academy of Sciences of Belarus

Abstract: In this paper we present a space-efficient algorithmic framework for solving construction variants of problems on graphs with bounded pathwidth. Algorithms for solving the $\lambda$-path cover problems and the problem of finding a minimum-weight Hamiltonian cycle on this type of graphs in $O(n\log n)$ time with $O(1)$ additional memory are given. An algorithm for solving 3-SAT with formulas having pathwidth-k interaction graphs in $O(n\log n)$ time with $O(1)$ additional memory is present.

UDC: 519.1

Received: 30.12.2009