RUS  ENG JOURNALS   PEOPLE   ORGANISATIONS   CONFERENCES   SEMINARS   VIDEO LIBRARY   PACKAGE AMSBIB
 General information Latest issue Archive Search papers Search references RSS Latest issue Current issues Archive issues What is RSS

 Tr. Inst. Mat.: Year: Volume: Issue: Page: Find

 Tr. Inst. Mat., 2011, Volume 19, Number 1, Pages 71–84 (Mi timb141)

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.

Full text: PDF file (217 kB)
References: PDF file   HTML file
UDC: 519.1

Citation: V. V. Lepin, “On cycle covers of graphs with bounded pathwidth”, Tr. Inst. Mat., 19:1 (2011), 71–84

Citation in format AMSBIB
\Bibitem{Lep11} \by V.~V.~Lepin \paper On cycle covers of graphs with bounded pathwidth \jour Tr. Inst. Mat. \yr 2011 \vol 19 \issue 1 \pages 71--84 \mathnet{http://mi.mathnet.ru/timb141}