Geodesic
On cycle covers of graphs with bounded pathwidth
Trudy Instituta matematiki, Tome 19 (2011) no. 1, pp. 71-84.

Voir la notice de l'article provenant de la source Math-Net.Ru

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. 
@article{TIMB_2011_19_1_a7,
     author = {V. V. Lepin},
     title = {On cycle covers of graphs with bounded pathwidth},
     journal = {Trudy Instituta matematiki},
     pages = {71--84},
     publisher = {mathdoc},
     volume = {19},
     number = {1},
     year = {2011},
     language = {ru},
     url = {http://geodesic.mathdoc.fr/item/TIMB_2011_19_1_a7/}
}
TY  - JOUR
AU  - V. V. Lepin
TI  - On cycle covers of graphs with bounded pathwidth
JO  - Trudy Instituta matematiki
PY  - 2011
SP  - 71
EP  - 84
VL  - 19
IS  - 1
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/item/TIMB_2011_19_1_a7/
LA  - ru
ID  - TIMB_2011_19_1_a7
ER  - 
%0 Journal Article
%A V. V. Lepin
%T On cycle covers of graphs with bounded pathwidth
%J Trudy Instituta matematiki
%D 2011
%P 71-84
%V 19
%N 1
%I mathdoc
%U http://geodesic.mathdoc.fr/item/TIMB_2011_19_1_a7/
%G ru
%F TIMB_2011_19_1_a7
V. V. Lepin. On cycle covers of graphs with bounded pathwidth. Trudy Instituta matematiki, Tome 19 (2011) no. 1, pp. 71-84. http://geodesic.mathdoc.fr/item/TIMB_2011_19_1_a7/

[1] Lovas L., Plammer M., Prikladnye zadachi teorii grafov. Teoriya parosochetanii v matematike, fizike, khimii., M., 1998

[2] Pulleyblank W. R., “Matchings and extensions”, Handbook of Combinatorics, v. 1, eds. R. L. Graham, M. Grotschel, and L. Lovasz, Elsevier, Amsterdam, 1995, 179–232 | MR | Zbl

[3] Geri M., Dzhonson D., Vychislitelnye mashiny i trudnoreshaemye zadachi, M., 1982 | MR

[4] Krishnamoorthy M.S., “An NP-Hard Problem in Bipartite Graphs”, SIGACT News, 7:1 (1975), 26 | DOI | MR

[5] Garey M.R., Johnson D.S., Tarjan R.E., “The planar Hamiltonian circuit problem is NP-complete”, SIAM J. Comput., 5 (1976), 704–714 | DOI | MR | Zbl

[6] Chvatal V., “Hamiltonian cycles”, The Traveling Salesman Problem: A Guided Tour of Combinatorial Optimization, eds. E.L. Lawler, J.K. Lenstra, A.H.G. Rinnooy Kan, and D.B. Shmoys, John Wiley Sons Ltd., New York, 1985, 403–429 | MR

[7] Wigderson A., The Complexity Of The Hamiltonian Circuit Problem For Maximal Planar Graphs, Technical Report, Princeton University, Dept. of EECS, V. 298, February, 1982.

[8] Müller H., “Hamiltonian circuits in chordal bipartite graphs”, Discrete Math., 156 (1996), 291–298 | DOI | MR

[9] Picouleau C., “Complexity of the Hamiltonian cycle in regular graph problem”, Theoretical computer science, 131(2) (1994), 463–473 | DOI | MR | Zbl

[10] Robertson N., Seymour D., “Graph Minor II. Algorithmic aspects of tree width”, J. Algorithms, 7 (1986), 309–322 | DOI | MR | Zbl

[11] Bodlaender H.L., “A linear-time algorithm for finding tree decompositions of small treewidth”, SIAM J. Comput., 25 (1996), 1305–1317 | DOI | MR | Zbl

[12] Cattell K., Dinneen M.J., Fellows M.R., “A simple linear-time algorithm for finding path-decompositions of small width”, Inform. Process. Lett., 57:4 (1996), 197–203 | DOI | MR | Zbl

[13] Perkovic' L., Reed B., “An Improved Algorithm for Finding Tree Decompositions of Small Width”, Lecture Notes In Computer Science, 1665, 1999, 148–154 | MR | Zbl

[14] Diaz J., Petit J., Serna M., “A survey of graph layout problems”, ACM Comput. Surveys, 34:3 (2002), 313–356 | DOI

[15] Kinnersley N.G., “The vertex separation number of a graph equals its path-width”, Inform. Process. Lett., 42:6 (1992), 345–350 | DOI | MR | Zbl

[16] Lepin V.V., “Reshenie zadach v klasse frontalno-ogranichennykh grafov”, Vestsi AN Belarusi. Ser. fiz.-mat. navuk, 1996, no. 3, 101–105 | MR | Zbl

[17] Bodlaender H.L., Kloks T., “Efficient and constructive algorithms for the pathwidth and treewidth of graphs”, J. Algorithms, 21 (1996), 358–402 | DOI | MR | Zbl

[18] Courcelle B., “The monadic second-order logic of graphs I: Recognizable sets of finite graphs”, Information and Computation, 85 (1990), 12–75 | DOI | MR | Zbl

[19] Wolle T., “A Framework for Network Reliability Problems on Graphs of Bounded Treewidth”, LNCS, 2518 (2002), 401–420 | MR

[20] Andreica M. I., “A Dynamic Programming Framework for Combinatorial Optimization Problems on Graphs with Bounded Pathwidth”, Proceedings of the IEEE International Conference on Automation, Quality and Testing, Robotics (THETA 16) (AQTR) – Poster Session, 2008, 120–125

[21] Lepin V.V., “Algoritmy resheniya zadach na grafakh s ogranichennoi putevoi shirinoi”, Trudy Instituta matematiki, 18:1 (2010), 53–71

[22] Bodlaender H.L., Koster A.M.C.A., “Combinatorial Optimization on Graphs of Bounded Treewidth”, The Computer Journal, 51:3 (2008), 255–269 | DOI | MR