Vertex disjoint paths on clique-width bounded graphs

S. Alstrup, C. Gavoille, H. Kaplan, T. Rauhe, Nearest common ancestors: A survey and a new distributed algorithm. in: Proc. Annu. ACM Symp. Parallel Algorithms and Architectures, ACM, 2002, pp. 258–264. Bodlaender, 1990, Polynomial algorithms for chromatic index and graph isomorphism on partial k-trees, J. Algorithms, 11, 631, 10.1016/0196-6774(90)90013-5 A. Brandstädt, F.F. Dragan, H.-O. Le, R. Mosca, New graph classes of bounded clique width, in: Proc. Graph-Theoretical Concepts in Computer Science, Lecture Notes in Computer Science, Vol. 2573, Springer, Berlin, 2002, pp. 57–67. D.G. Corneil, M. Habib, J.M. Lanlignel, B. Reed, U. Rotics, Polynomial time recognition of clique-width at most three graphs, in: Proc. Latin American Symp. on Theoretical Informatics, Lecture Notes in Computer Science, Vol. 1776, Springer, Berlin, 2000, pp. 126–134. Corneil, 1985, A linear recognition algorithm for cographs, SIAM J. Comput., 14, 926, 10.1137/0214065 D.G. Corneil, U. Rotics, On the relationship between clique-width and treewidth, in: Proc. Graph-Theoretical Concepts in Computer Science, Lecture Notes in Computer Science, Vol. 2204, Springer, Berlin, 2001, pp. 78–90. Courcelle, 2000, Linear time solvable optimization problems on graphs of bounded clique-width, Theory Comput. Systems, 33, 125, 10.1007/s002249910009 Courcelle, 2000, Upper bounds to the clique width of graphs, Discrete Appl. Math., 101, 77, 10.1016/S0166-218X(99)00184-5 W. Espelage, F. Gurski, E. Wanke, How to solve NP-hard graph problems on clique-width bounded graphs in polynomial time, in: Proc. Graph-Theoretical Concepts in Computer Science, Lecture Notes in Computer Science, Vol. 2204, Springer, Berlin, 2001, pp. 117–128. Espelage, 2003, Deciding clique-width for graphs of bounded tree-width, J. Graph Algorithms Appl.—Special Issue JGAA WADS, 2001 7, 141, 10.7155/jgaa.00065 Even, 1976, On the complexity of timetable and multicommodity flow problems, SIAM J. Comput., 5, 691, 10.1137/0205048 T. Feder, R. Motwani, Clique partitions, graph compression and speeding up algorithms, in: Proc. Annu. ACM Symp. on Theory of Computing, ACM, 1991, pp. 123–133. M.R. Fellows, F.A. Rosamund, U. Rotics, S. Szeider, Proving NP-hardness for clique-width I: non-approximability of sequential clique-width, Technical Report TR05-080, ECCC, 2005. M.R. Fellows, F.A. Rosamund, U. Rotics, S. Szeider, Proving NP-hardness for clique-width II: non-approximability of clique-width, Technical Report TR05-081, ECCC, 2005. Golumbic, 2000, On the clique-width of some perfect graph classes, Internat. J. Found. Comput. Sci., 11, 423, 10.1142/S0129054100000260 F. Gurski, E. Wanke, The tree-width of clique-width bounded graphs without Kn,n, in: Proc. Graph-Theoret. Concepts in Computer Science, Lecture Notes in Computer Science, Vol. 1938, Springer, Berlin, 2000, pp. 196–205. F. Gurski, E. Wanke, Minimizing NLC-width is NP-complete (Extended Abstract), in: Proc. Graph-Theoretical Concepts in Computer Science, Lecture Notes in Computer Science, Vol. 3787, Springer, Berlin, 2005, pp. 69–80. Johansson, 1998, Clique-decomposition, NLC-decomposition, and modular decomposition—relationships and results for random graphs, Congr. Numer., 132, 39 Johansson, 2000, NLC2-decomposition in polynomial time, Internat. J. Found. Comput. Sci., 11, 373, 10.1142/S0129054100000223 Kobler, 2003, Edge dominating set and colorings on graphs with fixed clique-width, Discrete Appl. Math., 126, 197, 10.1016/S0166-218X(02)00198-1 Middendorf, 1995, On the complexity of the disjoint paths problems, Combinatorica, 35, 97, 10.1007/BF01202792 Nishizeki, 2001, The edge-disjoint paths problem is NP-complete for series-parallel graphs, Discrete Appl. Math., 115, 177, 10.1016/S0166-218X(01)00223-2 S.-I. Oum, P.D. Seymour, Approximating clique-width and branch-width, J. Combin. Theory, Ser. B, 2006, to appear. Robertson, 1986, Graph minors II. Algorithmic aspects of tree width, J. Algorithms, 7, 309, 10.1016/0196-6774(86)90023-4 Robertson, 1995, Graph minors XII. The disjoint paths problem, J. Combin. Theory, Ser. B, 63, 65, 10.1006/jctb.1995.1006 Rose, 1974, On simple characterizations of k-trees, Discrete Math., 7, 317, 10.1016/0012-365X(74)90042-9 P. Scheffler, A practical linear time algorithm for vertex disjoint paths in graphs with bounded treewidth, Technical Report 396, Department of Mathematics, Technische Universität Berlin, 1994. I. Todinca, Coloring powers of graphs of bounded clique-width, in: Proc. Graph-Theoret. Concepts in Computer Science, Lecture Notes in Computer Science, Vol. 2880, Springer, Berlin, 2003, pp. 370–382. Wanke, 1994, k-NLC graphs and polynomial algorithms, Discrete Appl. Math., 54, 251, 10.1016/0166-218X(94)90026-4