Geodesic
Algorithms for solving problems on graphs of bounded pathwidth
Trudy Instituta matematiki, Tome 18 (2010) no. 1, pp. 53-71.

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

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

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

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

[3] 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

[4] 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

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

[6] 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

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

[8] 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

[9] 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

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

[11] 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

[12] 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

[13] Golumbic M.C., Algorithmic Graph Theory and Perfect Graphs, Academic Press, New York, 1980, 284 pp. | MR

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

[15] Jung H.A., “On a class of posets and the corresponding comparability graphs”, J. Combin. Theory Ser. B, 35 (1978), 125–133 | DOI | MR

[16] Skupien Z., “Path partitions of vertices and Hamiltonicity of graphs”, Proceedings of the Second Czechoslovakian Symposium on Graph Theory, Prague, 1974, 481–491 | MR

[17] Arikati S.R., Pandu Rangan C., “Linear algorithm for optimal path cover problem on interval graphs”, Inform. Process. Lett., 35 (1990), 149–153 | DOI | MR | Zbl

[18] Bonuccelli M.A., Bovet D.P., “Minimum node disjoint path covering for circular-arc graphs”, Inform. Process. Lett., 8 (1979), 159–161 | DOI | MR | Zbl

[19] Chang G.J., Kuo D., “The $L(2;1)$-labeling problem on graphs”, SIAM J. Discrete Math., 9 (1996), 309–316 | DOI | MR | Zbl

[20] Corneil D.G., Lerchs H., Stewart L., “Complement reducible graphs”, Discrete Appl. Math., 3 (1981), 163–174 | DOI | MR | Zbl

[21] Srikant R., Sundaram R., Singh K.S., Rangan C.P., “Optimal path cover problem on block graphs and bipartite permutation graphs”, Theor. Comput. Sci., 115 (1993), 351–357 | DOI | MR | Zbl

[22] Yan J.-H., Chang G.J., “The path-partition problem in block graphs”, Inform. Process. Lett., 52 (1994), 317–322 | DOI | MR

[23] Wong P.-K., “Optimal path cover problem on block graphs”, Theor. Comput. Sci., 225:1-2 (1999), 163–169 | DOI | MR | Zbl

[24] Yeh H.-G., Chang G.J., “The path-partition problem in bipartite distance-hereditary graphs”, Taiwanese J. Math., 2:3 (1998), 353–360 | MR | Zbl

[25] Yan J.-H., Chang G.J., Hedetniemi S.M., Hedetniemi S.T., “k-Path partitions in trees”, Discrete Appl. Math., 78 (1997), 227–233 | DOI | MR | Zbl

[26] Steiner G., “On the k-Path partition problem in cographs”, Cong. Numer., 147 (2000), 89–96 | MR

[27] Steiner G., “On the k-path partition of graphs”, Theor. Comput. Sci., 290 (2003), 2147–2155 | DOI | MR | Zbl

[28] Moran S., Wolfstahl Y., “Optimal covering of cacti by vertex-disjoint paths”, Theoret. Comput. Sci., 84 (1991), 179–197 | DOI | MR | Zbl

[29] Jin Z., Li X., “On the k-path cover problem for cacti”, Theoretical Computer Science, 355:3 (2006), 354–363 | DOI | MR | Zbl

[30] Apolonnio N., Caccetta L., Simeone B., “Cardinality constrained path covering problems in grid graphs”, Networks, 44 (2006), 120–131 | DOI | MR

[31] Asdre K., Nikolopoulos S.D., Papadopoulos C., “An optimal parallel solution for the path cover problem on $P_4$-sparse graphs”, J. Parallel Distrib. Comput., 67 (2007), 63–76 | DOI | Zbl

[32] Cai YG, Zhang XZ, Qian JX, Sun YX, “An $O(n)$ algorithm for $\omega$-path partition of edge-weighted forests”, J. Software, 14 (2003), 897–903 | MR