{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,3,5]],"date-time":"2026-03-05T13:32:01Z","timestamp":1772717521937,"version":"3.50.1"},"publisher-location":"Berlin, Heidelberg","reference-count":145,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"value":"9783642308901","type":"print"},{"value":"9783642308918","type":"electronic"}],"license":[{"start":{"date-parts":[[2012,1,1]],"date-time":"2012-01-01T00:00:00Z","timestamp":1325376000000},"content-version":"unspecified","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2012]]},"DOI":"10.1007\/978-3-642-30891-8_12","type":"book-chapter","created":{"date-parts":[[2012,6,18]],"date-time":"2012-06-18T05:24:05Z","timestamp":1339997045000},"page":"196-227","source":"Crossref","is-referenced-by-count":9,"title":["Fixed-Parameter Tractability of Treewidth and Pathwidth"],"prefix":"10.1007","author":[{"given":"Hans L.","family":"Bodlaender","sequence":"first","affiliation":[]}],"member":"297","reference":[{"key":"12_CR1","doi-asserted-by":"publisher","first-page":"448","DOI":"10.1007\/s00453-008-9180-4","volume":"56","author":"E. Amir","year":"2010","unstructured":"Amir, E.: Approximation algorithms for treewidth. Algorithmica\u00a056, 448\u2013479 (2010)","journal-title":"Algorithmica"},{"key":"12_CR2","doi-asserted-by":"publisher","first-page":"39","DOI":"10.1016\/S0012-365X(98)00113-7","volume":"190","author":"A. Andrzejak","year":"1998","unstructured":"Andrzejak, A.: An algorithm for the Tutte polynomials of graphs of bounded treewidth. Discrete Mathematics\u00a0190, 39\u201354 (1998)","journal-title":"Discrete Mathematics"},{"key":"12_CR3","doi-asserted-by":"publisher","first-page":"2","DOI":"10.1007\/BF01934985","volume":"25","author":"S. Arnborg","year":"1985","unstructured":"Arnborg, S.: Efficient algorithms for combinatorial problems on graphs with bounded decomposability \u2013 A survey. BIT\u00a025, 2\u201323 (1985)","journal-title":"BIT"},{"key":"12_CR4","doi-asserted-by":"publisher","first-page":"277","DOI":"10.1137\/0608024","volume":"8","author":"S. Arnborg","year":"1987","unstructured":"Arnborg, S., Corneil, D.G., Proskurowski, A.: Complexity of finding embeddings in a k-tree. SIAM Journal on Algebraic and Discrete Methods\u00a08, 277\u2013284 (1987)","journal-title":"SIAM Journal on Algebraic and Discrete Methods"},{"key":"12_CR5","doi-asserted-by":"publisher","first-page":"1134","DOI":"10.1145\/174147.169807","volume":"40","author":"S. Arnborg","year":"1993","unstructured":"Arnborg, S., Courcelle, B., Proskurowski, A., Seese, D.: An algebraic theory of graph reduction. Journal of the ACM\u00a040, 1134\u20131164 (1993)","journal-title":"Journal of the ACM"},{"key":"12_CR6","doi-asserted-by":"publisher","first-page":"308","DOI":"10.1016\/0196-6774(91)90006-K","volume":"12","author":"S. Arnborg","year":"1991","unstructured":"Arnborg, S., Lagergren, J., Seese, D.: Easy problems for tree-decomposable graphs. Journal of Algorithms\u00a012, 308\u2013340 (1991)","journal-title":"Journal of Algorithms"},{"key":"12_CR7","doi-asserted-by":"publisher","first-page":"305","DOI":"10.1137\/0607033","volume":"7","author":"S. Arnborg","year":"1986","unstructured":"Arnborg, S., Proskurowski, A.: Characterization and recognition of partial 3-trees. SIAM Journal on Algebraic and Discrete Methods\u00a07, 305\u2013314 (1986)","journal-title":"SIAM Journal on Algebraic and Discrete Methods"},{"key":"12_CR8","doi-asserted-by":"publisher","first-page":"11","DOI":"10.1016\/0166-218X(89)90031-0","volume":"23","author":"S. Arnborg","year":"1989","unstructured":"Arnborg, S., Proskurowski, A.: Linear time algorithms for NP-hard problems restricted to partial k-trees. Discrete Applied Mathematics\u00a023, 11\u201324 (1989)","journal-title":"Discrete Applied Mathematics"},{"key":"12_CR9","doi-asserted-by":"publisher","first-page":"216","DOI":"10.1016\/0196-6774(87)90039-3","volume":"8","author":"M.W. Bern","year":"1987","unstructured":"Bern, M.W., Lawler, E.L., Wong, A.L.: Linear time computation of optimal subgraphs of decomposable graphs. Journal of Algorithms\u00a08, 216\u2013235 (1987)","journal-title":"Journal of Algorithms"},{"key":"12_CR10","first-page":"481","volume-title":"Handbook of Operations Research and Management Science: Network Models","author":"D. Bienstock","year":"1995","unstructured":"Bienstock, D., Langston, M.A.: Algorithmic implications of the graph minor theorem. In: Ball, M.O., Magnanti, T.L., Monma, C.L., Nemhauser, G.L. (eds.) Handbook of Operations Research and Management Science: Network Models, pp. 481\u2013502. North-Holland, Amsterdam (1995)"},{"key":"12_CR11","doi-asserted-by":"publisher","first-page":"274","DOI":"10.1016\/0095-8956(91)90068-U","volume":"52","author":"D. Bienstock","year":"1991","unstructured":"Bienstock, D., Robertson, N., Seymour, P.D., Thomas, R.: Quickly excluding a forest. Journal of Combinatorial Theory, Series B\u00a052, 274\u2013283 (1991)","journal-title":"Journal of Combinatorial Theory, Series B"},{"key":"12_CR12","doi-asserted-by":"publisher","first-page":"631","DOI":"10.1016\/0196-6774(90)90013-5","volume":"11","author":"H.L. Bodlaender","year":"1990","unstructured":"Bodlaender, H.L.: Polynomial algorithms for graph isomorphism and chromatic index on partial k-trees. Journal of Algorithms\u00a011, 631\u2013643 (1990)","journal-title":"Journal of Algorithms"},{"key":"12_CR13","doi-asserted-by":"publisher","first-page":"101","DOI":"10.1016\/0166-218X(94)90018-3","volume":"54","author":"H.L. Bodlaender","year":"1994","unstructured":"Bodlaender, H.L.: Improved self-reduction algorithms for graphs with bounded treewidth. Discrete Applied Mathematics\u00a054, 101\u2013115 (1994)","journal-title":"Discrete Applied Mathematics"},{"key":"12_CR14","doi-asserted-by":"publisher","first-page":"1305","DOI":"10.1137\/S0097539793251219","volume":"25","author":"H.L. Bodlaender","year":"1996","unstructured":"Bodlaender, H.L.: A linear time algorithm for finding tree-decompositions of small treewidth. SIAM Journal on Computing\u00a025, 1305\u20131317 (1996)","journal-title":"SIAM Journal on Computing"},{"key":"12_CR15","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"19","DOI":"10.1007\/BFb0029946","volume-title":"Mathematical Foundations of Computer Science 1997","author":"H.L. Bodlaender","year":"1997","unstructured":"Bodlaender, H.L.: Treewidth: Algorithmic Techniques and Results. In: Privara, I., Ru\u017ei\u010dka, P. (eds.) MFCS 1997. LNCS, vol.\u00a01295, pp. 19\u201336. Springer, Heidelberg (1997)"},{"key":"12_CR16","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1016\/S0304-3975(97)00228-4","volume":"209","author":"H.L. Bodlaender","year":"1998","unstructured":"Bodlaender, H.L.: A partial k-arboretum of graphs with bounded treewidth. Theoretical Computer Science\u00a0209, 1\u201345 (1998)","journal-title":"Theoretical Computer Science"},{"key":"12_CR17","doi-asserted-by":"publisher","first-page":"423","DOI":"10.1016\/j.jcss.2009.04.001","volume":"75","author":"H.L. Bodlaender","year":"2009","unstructured":"Bodlaender, H.L., Downey, R.G., Fellows, M.R., Hermelin, D.: On problems without polynomial kernels. Journal of Computer and System Sciences\u00a075, 423\u2013434 (2009)","journal-title":"Journal of Computer and System Sciences"},{"key":"12_CR18","doi-asserted-by":"publisher","first-page":"167","DOI":"10.1016\/S0304-3975(98)00342-9","volume":"244","author":"H.L. Bodlaender","year":"2000","unstructured":"Bodlaender, H.L., Fellows, M.R., Hallett, M.T., Wareham, H.T., Warnow, T.J.: The hardness of perfect phylogeny, feasible register assignment and other problems on thin colored graphs. Theoretical Computer Science\u00a0244, 167\u2013188 (2000)","journal-title":"Theoretical Computer Science"},{"key":"12_CR19","doi-asserted-by":"publisher","first-page":"231","DOI":"10.1016\/j.jcss.2008.10.003","volume":"75","author":"H.L. Bodlaender","year":"2009","unstructured":"Bodlaender, H.L., Fellows, M.R., Thilikos, D.M.: Derivation of algorithms for cutwidth and related graph layout parameters. Journal of Computer and System Sciences\u00a075, 231\u2013244 (2009)","journal-title":"Journal of Computer and System Sciences"},{"key":"12_CR20","doi-asserted-by":"crossref","unstructured":"Bodlaender, H.L., Fomin, F.V., Lokshtanov, D., Penninkx, E., Saurabh, S., Thilikos, D.M.: (Meta) kernelization. In: Proceedings of the 50th Annual Symposium on Foundations of Computer Science, FOCS 2009, pp. 629\u2013638. IEEE Computer Society (2009)","DOI":"10.1109\/FOCS.2009.46"},{"key":"12_CR21","doi-asserted-by":"publisher","first-page":"238","DOI":"10.1006\/jagm.1995.1009","volume":"18","author":"H.L. Bodlaender","year":"1995","unstructured":"Bodlaender, H.L., Gilbert, J.R., Hafsteinsson, H., Kloks, T.: Approximating treewidth, pathwidth, frontsize, and minimum elimination tree height. Journal of Algorithms\u00a018, 238\u2013255 (1995)","journal-title":"Journal of Algorithms"},{"key":"12_CR22","doi-asserted-by":"publisher","first-page":"1725","DOI":"10.1137\/S0097539795289859","volume":"27","author":"H.L. Bodlaender","year":"1998","unstructured":"Bodlaender, H.L., Hagerup, T.: Parallel algorithms with optimal speedup for bounded treewidth. SIAM J. Comput.\u00a027, 1725\u20131746 (1998)","journal-title":"SIAM J. Comput."},{"key":"12_CR23","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"437","DOI":"10.1007\/978-3-642-22006-7_37","volume-title":"Automata, Languages and Programming","author":"H.L. Bodlaender","year":"2011","unstructured":"Bodlaender, H.L., Jansen, B.M.P., Kratsch, S.: Preprocessing for Treewidth: A Combinatorial Analysis through Kernelization. In: Aceto, L., Henzinger, M., Sgall, J. (eds.) ICALP 2011, Part I. LNCS, vol.\u00a06755, pp. 437\u2013448. Springer, Heidelberg (2011)"},{"key":"12_CR24","doi-asserted-by":"publisher","first-page":"358","DOI":"10.1006\/jagm.1996.0049","volume":"21","author":"H.L. Bodlaender","year":"1996","unstructured":"Bodlaender, H.L., Kloks, T.: Efficient and constructive algorithms for the pathwidth and treewidth of graphs. Journal of Algorithms\u00a021, 358\u2013402 (1996)","journal-title":"Journal of Algorithms"},{"key":"12_CR25","doi-asserted-by":"publisher","first-page":"259","DOI":"10.1016\/j.ic.2009.03.008","volume":"208","author":"H.L. Bodlaender","year":"2010","unstructured":"Bodlaender, H.L., Koster, A.M.C.A.: Treewidth computations I. Upper bounds. Information and Computation\u00a0208, 259\u2013275 (2010)","journal-title":"Information and Computation"},{"key":"12_CR26","doi-asserted-by":"publisher","first-page":"1103","DOI":"10.1016\/j.ic.2011.04.003","volume":"209","author":"H.L. Bodlaender","year":"2011","unstructured":"Bodlaender, H.L., Koster, A.M.C.A.: Treewidth computations II. Lower bounds. Information and Computation\u00a0209, 1103\u20131119 (2011)","journal-title":"Information and Computation"},{"issue":"3","key":"12_CR27","doi-asserted-by":"publisher","first-page":"286","DOI":"10.1111\/j.1467-8640.2005.00274.x","volume":"21","author":"H.L. Bodlaender","year":"2005","unstructured":"Bodlaender, H.L., Koster, A.M.C.A., Van den Eijkhof, F.: Pre-processing rules for triangulation of probabilistic networks. Computational Intelligence\u00a021(3), 286\u2013305 (2005)","journal-title":"Computational Intelligence"},{"key":"12_CR28","doi-asserted-by":"publisher","first-page":"181","DOI":"10.1137\/0406014","volume":"6","author":"H.L. Bodlaender","year":"1993","unstructured":"Bodlaender, H.L., M\u00f6hring, R.H.: The pathwidth and treewidth of cographs. SIAM Journal on Discrete Mathematics\u00a06, 181\u2013188 (1993)","journal-title":"SIAM Journal on Discrete Mathematics"},{"key":"12_CR29","doi-asserted-by":"publisher","first-page":"86","DOI":"10.1006\/inco.2000.2958","volume":"167","author":"H.L. Bodlaender","year":"2001","unstructured":"Bodlaender, H.L., van Antwerpen-de Fluiter, B.: Reduction algorithms for graphs of small treewidth. Information and Computation\u00a0167, 86\u2013119 (2001)","journal-title":"Information and Computation"},{"key":"12_CR30","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"174","DOI":"10.1007\/978-3-642-15155-2_17","volume-title":"Mathematical Foundations of Computer Science 2010","author":"H.L. Bodlaender","year":"2010","unstructured":"Bodlaender, H.L., van Leeuwen, E.J., van Rooij, J.M.M., Vatshelle, M.: Faster Algorithms on Branch and Clique Decompositions. In: Hlin\u011bn\u00fd, P., Ku\u010dera, A. (eds.) MFCS 2010. LNCS, vol.\u00a06281, pp. 174\u2013185. Springer, Heidelberg (2010)"},{"key":"12_CR31","doi-asserted-by":"publisher","first-page":"123","DOI":"10.1007\/BF01293664","volume":"14","author":"R.B. Borie","year":"1995","unstructured":"Borie, R.B.: Generation of polynomial-time algorithms for some optimization problems on tree-decomposable graphs. Algorithmica\u00a014, 123\u2013137 (1995)","journal-title":"Algorithmica"},{"key":"12_CR32","doi-asserted-by":"publisher","first-page":"555","DOI":"10.1007\/BF01758777","volume":"7","author":"R.B. Borie","year":"1992","unstructured":"Borie, R.B., Parker, R.G., Tovey, C.A.: Automatic generation of linear-time algorithms from predicate calculus descriptions of problems on recursively constructed graph families. Algorithmica\u00a07, 555\u2013581 (1992)","journal-title":"Algorithmica"},{"key":"12_CR33","doi-asserted-by":"crossref","unstructured":"Borie, R.B., Parker, R.G., Tovey, C.A.: Solving problems on recursively constructed graphs. ACM Computing Surveys\u00a041(4) (2008)","DOI":"10.1145\/1456650.1456654"},{"key":"12_CR34","doi-asserted-by":"publisher","first-page":"212","DOI":"10.1137\/S0097539799359683","volume":"31","author":"V. Bouchitt\u00e9","year":"2001","unstructured":"Bouchitt\u00e9, V., Todinca, I.: Treewidth and minimum fill-in: Grouping the minimal separators. SIAM Journal on Computing\u00a031, 212\u2013232 (2001)","journal-title":"SIAM Journal on Computing"},{"key":"12_CR35","doi-asserted-by":"publisher","first-page":"17","DOI":"10.1016\/S0304-3975(01)00007-X","volume":"276","author":"V. Bouchitt\u00e9","year":"2002","unstructured":"Bouchitt\u00e9, V., Todinca, I.: Listing all potential maximal cliques of a graph. Theoretical Computer Science\u00a0276, 17\u201332 (2002)","journal-title":"Theoretical Computer Science"},{"key":"12_CR36","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1080\/00207168908803783","volume":"31","author":"D.J. Brown","year":"1989","unstructured":"Brown, D.J., Fellows, M.R., Langston, M.A.: Polynomial-time self-reducibility: Theoretical motivations and practical results. International Journal of Computer Mathematics\u00a031, 1\u20139 (1989)","journal-title":"International Journal of Computer Mathematics"},{"key":"12_CR37","doi-asserted-by":"publisher","first-page":"107","DOI":"10.1016\/S0304-3975(97)00300-9","volume":"233","author":"K. Cattell","year":"2000","unstructured":"Cattell, K., Dinneen, M.J., Downey, R.G., Fellows, M.R., Langston, M.A.: On computing graph minor obstruction sets. Theoretical Computer Science\u00a0233, 107\u2013127 (2000)","journal-title":"Theoretical Computer Science"},{"key":"12_CR38","doi-asserted-by":"publisher","first-page":"205","DOI":"10.1016\/S0304-3975(98)00021-8","volume":"203","author":"S. Chaudhuri","year":"1998","unstructured":"Chaudhuri, S., Zaroliagis, C.D.: Shortest paths in digraphs of small treewidth. Part II: Optimal parallel algorithms. Theoretical Computer Science\u00a0203, 205\u2013223 (1998)","journal-title":"Theoretical Computer Science"},{"key":"12_CR39","doi-asserted-by":"publisher","first-page":"212","DOI":"10.1007\/s004530010016","volume":"27","author":"S. Chaudhuri","year":"2000","unstructured":"Chaudhuri, S., Zaroliagis, C.D.: Shortest paths in digraphs of small treewidth. Part I: Sequential algorithms. Algorithmica\u00a027, 212\u2013226 (2000)","journal-title":"Algorithmica"},{"key":"12_CR40","unstructured":"Chen, H.: Quantified constraint satisfaction and bounded treewidth. In: de M\u00e1ntaras, R.L., Saitta, L. (eds.) Proceedings of the 17th European Conference on Artificial Intelligence, ECAI 2004, pp. 161\u2013165 (2004)"},{"key":"12_CR41","volume-title":"Introduction to Algorithms","author":"T.H. Cormen","year":"2001","unstructured":"Cormen, T.H., Leiserson, C.E., Rivest, R.L., Stein, C.: Introduction to Algorithms, 2nd edn. MIT Press, Cambridge (2001)","edition":"2"},{"key":"12_CR42","doi-asserted-by":"publisher","first-page":"12","DOI":"10.1016\/0890-5401(90)90043-H","volume":"85","author":"B. Courcelle","year":"1990","unstructured":"Courcelle, B.: The monadic second-order logic of graphs I: Recognizable sets of finite graphs. Information and Computation\u00a085, 12\u201375 (1990)","journal-title":"Information and Computation"},{"key":"12_CR43","doi-asserted-by":"publisher","first-page":"153","DOI":"10.1016\/0304-3975(91)90387-H","volume":"80","author":"B. Courcelle","year":"1991","unstructured":"Courcelle, B.: The monadic second-order logic of graphs V: On closing the gap between definability and recognizability. Theoretical Computer Science\u00a080, 153\u2013202 (1991)","journal-title":"Theoretical Computer Science"},{"key":"12_CR44","first-page":"125","volume":"33","author":"B. Courcelle","year":"2000","unstructured":"Courcelle, B., Makowsky, J.A., Rotics, U.: Linear time solvable optimization problems on graphs of bounded clique width. Theoretical Computer Science\u00a033, 125\u2013150 (2000)","journal-title":"Theoretical Computer Science"},{"key":"12_CR45","doi-asserted-by":"publisher","first-page":"49","DOI":"10.1016\/0304-3975(93)90064-Z","volume":"109","author":"B. Courcelle","year":"1993","unstructured":"Courcelle, B., Mosbah, M.: Monadic second-order evaluations on tree-decomposable graphs. Theoretical Computer Science\u00a0109, 49\u201382 (1993)","journal-title":"Theoretical Computer Science"},{"key":"12_CR46","doi-asserted-by":"crossref","unstructured":"Cygan, M., Nederlof, J., Pilipczuk, M., Pilipczuk, M., van Rooij, J., Wojtaszczyk, J.O.: Solving connectivity problems parameterized by treewidth in single exponential time. In: Proceedings of the 52nd Annual Symposium on Foundations of Computer Science, FOCS 2011, pp. 150\u2013159 (2011)","DOI":"10.1109\/FOCS.2011.23"},{"key":"12_CR47","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"310","DOI":"10.1007\/3-540-46135-3_21","volume-title":"Principles and Practice of Constraint Programming - CP 2002","author":"V. Dalmau","year":"2002","unstructured":"Dalmau, V., Kolaitis, P.G., Vardi, M.Y.: Constraint Satisfaction, Bounded Treewidth, and Finite-Variable Logics. In: Van Hentenryck, P. (ed.) CP 2002. LNCS, vol.\u00a02470, pp. 310\u2013326. Springer, Heidelberg (2002)"},{"key":"12_CR48","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"313","DOI":"10.1007\/978-3-642-14186-7_27","volume-title":"Theory and Applications of Satisfiability Testing \u2013 SAT 2010","author":"E. Dantsin","year":"2010","unstructured":"Dantsin, E., Wolpert, A.: On Moderately Exponential Time for SAT. In: Strichman, O., Szeider, S. (eds.) SAT 2010. LNCS, vol.\u00a06175, pp. 313\u2013325. Springer, Heidelberg (2010)"},{"key":"12_CR49","unstructured":"de\u00a0Fluiter, B.: Algorithms for Graphs of Small Treewidth. PhD thesis, Utrecht University (1997)"},{"key":"12_CR50","doi-asserted-by":"publisher","first-page":"291","DOI":"10.1016\/S0304-3975(02)00017-8","volume":"281","author":"J. D\u00edaz","year":"2002","unstructured":"D\u00edaz, J., Serna, M., Thilikos, D.M.: Counting H-colorings of partial k-trees. Theoretical Computer Science\u00a0281, 291\u2013309 (2002)","journal-title":"Theoretical Computer Science"},{"key":"12_CR51","doi-asserted-by":"publisher","first-page":"61","DOI":"10.1006\/jctb.1998.1862","volume":"75","author":"R. Diestel","year":"1999","unstructured":"Diestel, R., Jensen, T.R., Gorbunov, K.Y., Thomassen, C.: Highly connected sets and the excluded grid theorem. Journal of Combinatorial Theory, Series B\u00a075, 61\u201373 (1999)","journal-title":"Journal of Combinatorial Theory, Series B"},{"key":"12_CR52","doi-asserted-by":"publisher","first-page":"800","DOI":"10.1016\/j.dam.2009.10.011","volume":"158","author":"F. Dorn","year":"2010","unstructured":"Dorn, F.: Dynamic programming and planarity: Improved tree-decomposition based algorithms. Discrete Applied Mathematics\u00a0158, 800\u2013808 (2010)","journal-title":"Discrete Applied Mathematics"},{"key":"12_CR53","doi-asserted-by":"publisher","first-page":"790","DOI":"10.1007\/s00453-009-9296-1","volume":"58","author":"F. Dorn","year":"2010","unstructured":"Dorn, F., Penninkx, E., Bodlaender, H.L., Fomin, F.V.: Efficient exact algorithms on planar graphs: Exploiting sphere cut decompositions. Algorithmica\u00a058, 790\u2013810 (2010)","journal-title":"Algorithmica"},{"key":"12_CR54","doi-asserted-by":"crossref","unstructured":"Downey, R.G., Fellows, M.R.: Parameterized Complexity. Springer (1999)","DOI":"10.1007\/978-1-4612-0515-9"},{"key":"12_CR55","doi-asserted-by":"crossref","unstructured":"Drucker, A.: New limits to classical and quantum instance compression (preliminary draft) (2012) (manuscript)","DOI":"10.1109\/FOCS.2012.71"},{"key":"12_CR56","first-page":"138","volume":"47","author":"F. Eijkhof van den","year":"2007","unstructured":"van den Eijkhof, F., Bodlaender, H.L., Koster, A.M.C.A.: Safe reduction rules for weighted treewidth. Algorithmica\u00a047, 138\u2013158 (2007)","journal-title":"Algorithmica"},{"key":"12_CR57","doi-asserted-by":"crossref","unstructured":"Elberfeld, M., Jakoby, A., Tantau, T.: Logspace versions of the theorems of Bodlaender and Courcelle. In: Proceedings of the 51st Annual Symposium on Foundations of Computer Science, FOCS 2010, pp. 143\u2013152 (2010)","DOI":"10.1109\/FOCS.2010.21"},{"key":"12_CR58","unstructured":"Ellis, J.A., Sudborough, I.H., Turner, J.: Graph separation and search number. Report DCS-66-IR, University of Victoria (1987)"},{"key":"12_CR59","doi-asserted-by":"publisher","first-page":"629","DOI":"10.1137\/05064299X","volume":"38","author":"U. Feige","year":"2008","unstructured":"Feige, U., Hajiaghayi, M., Lee, J.R.: Improved approximation algorithms for minimum weight vertex separators. SIAM Journal on Computing\u00a038, 629\u2013657 (2008)","journal-title":"SIAM Journal on Computing"},{"key":"12_CR60","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1090\/conm\/089\/1006472","volume":"89","author":"M.R. Fellows","year":"1989","unstructured":"Fellows, M.R.: The Robertson-Seymour theorems: A survey of applications. Contemporary Mathematics\u00a089, 1\u201318 (1989)","journal-title":"Contemporary Mathematics"},{"key":"12_CR61","first-page":"143","volume":"209","author":"M.R. Fellows","year":"2011","unstructured":"Fellows, M.R., Fomin, F.V., Lokshtanov, D., Rosamond, F., Saurabh, S., Szeider, S., Thomassen, C.: On the complexity of some colorful problems parameterized by treewidth. Information and Control\u00a0209, 143\u2013153 (2011)","journal-title":"Information and Control"},{"key":"12_CR62","doi-asserted-by":"publisher","first-page":"157","DOI":"10.1016\/0020-0190(87)90054-8","volume":"26","author":"M.R. Fellows","year":"1987","unstructured":"Fellows, M.R., Langston, M.A.: Nonconstructive advances in polynomial-time complexity. Information Processing Letters\u00a026, 157\u2013162 (1987)","journal-title":"Information Processing Letters"},{"key":"12_CR63","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"278","DOI":"10.1007\/BFb0040395","volume-title":"VLSI Algorithms and Architectures","author":"M.R. Fellows","year":"1988","unstructured":"Fellows, M.R., Langston, M.A.: Fast Self-reduction Algorithms for Combinatorial Problems of VLSI Design. In: Reif, J.H. (ed.) AWOC 1988. LNCS, vol.\u00a0319, pp. 278\u2013287. Springer, Heidelberg (1988)"},{"key":"12_CR64","doi-asserted-by":"publisher","first-page":"727","DOI":"10.1145\/44483.44491","volume":"35","author":"M.R. Fellows","year":"1988","unstructured":"Fellows, M.R., Langston, M.A.: Nonconstructive tools for proving polynomial-time decidability. Journal of the ACM\u00a035, 727\u2013739 (1988)","journal-title":"Journal of the ACM"},{"key":"12_CR65","doi-asserted-by":"crossref","unstructured":"Fellows, M.R., Langston, M.A.: An analogue of the Myhill-Nerode theorem and its use in computing finite-basis characterizations. In: Proceedings of the 30th Annual Symposium on Foundations of Computer Science, FOCS 1989, pp. 520\u2013525 (1989)","DOI":"10.1109\/SFCS.1989.63528"},{"key":"12_CR66","doi-asserted-by":"crossref","unstructured":"Fellows, M.R., Langston, M.A.: On search, decision and the efficiency of polynomial-time algorithms. In: Proceedings of the 21st Annual Symposium on Theory of Computing, STOC 1989, pp. 501\u2013512 (1989)","DOI":"10.1145\/73007.73055"},{"key":"12_CR67","first-page":"325","volume":"3","author":"M.R. Fellows","year":"1991","unstructured":"Fellows, M.R., Langston, M.A.: Fast search algorithms for layout permutation problems. International Journal on Computer Aided VLSI Design\u00a03, 325\u2013340 (1991)","journal-title":"International Journal on Computer Aided VLSI Design"},{"key":"12_CR68","doi-asserted-by":"publisher","first-page":"117","DOI":"10.1137\/0405010","volume":"5","author":"M.R. Fellows","year":"1992","unstructured":"Fellows, M.R., Langston, M.A.: On well-partial-order theory and its application to combinatorial problems of VLSI design. SIAM Journal on Discrete Mathematics\u00a05, 117\u2013126 (1992)","journal-title":"SIAM Journal on Discrete Mathematics"},{"key":"12_CR69","doi-asserted-by":"publisher","first-page":"769","DOI":"10.1016\/S0022-0000(05)80079-0","volume":"49","author":"M.R. Fellows","year":"1994","unstructured":"Fellows, M.R., Langston, M.A.: On search, decision and the efficiency of polynomial-time algorithms. Journal of Computer and System Sciences\u00a049, 769\u2013779 (1994)","journal-title":"Journal of Computer and System Sciences"},{"key":"12_CR70","doi-asserted-by":"publisher","first-page":"408","DOI":"10.1006\/jagm.1994.1019","volume":"16","author":"D. Fern\u00e1ndez-Baca","year":"1994","unstructured":"Fern\u00e1ndez-Baca, D., Slutzki, G.: Parametic problems on graphs of bounded treewidth. Journal of Algorithms\u00a016, 408\u2013430 (1994)","journal-title":"Journal of Algorithms"},{"key":"12_CR71","doi-asserted-by":"publisher","first-page":"181","DOI":"10.1007\/s00453-007-9133-3","volume":"54","author":"F.V. Fomin","year":"2009","unstructured":"Fomin, F.V., Gaspers, S., Saurabh, S., Stepanov, A.A.: On two techniques of combining branching and treewidth. Algorithmica\u00a054, 181\u2013207 (2009)","journal-title":"Algorithmica"},{"key":"12_CR72","doi-asserted-by":"crossref","unstructured":"Fomin, F.V., Lokshtanov, D., Saurabh, S., Thilikos, D.M.: Bidimensionality and kernels. In: Proceedings of the 20th Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2010, pp. 503\u2013510 (2010)","DOI":"10.1137\/1.9781611973075.43"},{"key":"12_CR73","doi-asserted-by":"crossref","unstructured":"Fomin, F.V., Lokshtanov, D., Saurabh, S., Thilikos, D.M.: Linear kernels for (connected) dominating set on H-minor-free graphs. In: Proceedings of the 22nd Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2012, pp. 82\u201393 (2012)","DOI":"10.1137\/1.9781611973099.7"},{"key":"12_CR74","doi-asserted-by":"publisher","first-page":"53","DOI":"10.1002\/jgt.20121","volume":"51","author":"F.V. Fomin","year":"2006","unstructured":"Fomin, F.V., Thilikos, D.M.: New upper bounds on the decomposability of planar graphs. Journal of Graph Theory\u00a051, 53\u201381 (2006)","journal-title":"Journal of Graph Theory"},{"key":"12_CR75","doi-asserted-by":"publisher","first-page":"229","DOI":"10.1090\/conm\/065\/891251","volume":"65","author":"H. Friedman","year":"1987","unstructured":"Friedman, H., Robertson, N., Seymour, P.D.: The metamathematics of the graph minor theorem. Contemporary Mathematics\u00a065, 229\u2013261 (1987)","journal-title":"Contemporary Mathematics"},{"key":"12_CR76","doi-asserted-by":"publisher","first-page":"851","DOI":"10.1016\/j.dam.2009.10.018","volume":"158","author":"R. Ganian","year":"2010","unstructured":"Ganian, R., Hlin\u011bn\u00fd, P.: On parse trees and Myhill-Nerode-type tools for handling graphs of bounded rank-width. Discrete Applied Mathematics\u00a0158, 851\u2013867 (2010)","journal-title":"Discrete Applied Mathematics"},{"key":"12_CR77","volume-title":"Algorithmic Graph Theory and Perfect Graphs","author":"M.C. Golumbic","year":"1980","unstructured":"Golumbic, M.C.: Algorithmic Graph Theory and Perfect Graphs. Academic Press, New York (1980)"},{"key":"12_CR78","first-page":"243","volume":"124","author":"G. Gottlob","year":"2000","unstructured":"Gottlob, G., Leone, N., Scarcello, F.: A comparison of structural CSP decomposition methods. Acta Informatica\u00a0124, 243\u2013282 (2000)","journal-title":"Acta Informatica"},{"key":"12_CR79","doi-asserted-by":"publisher","first-page":"287","DOI":"10.1016\/0304-3975(96)00046-1","volume":"164","author":"A. Gupta","year":"1996","unstructured":"Gupta, A., Nishimura, N.: The complexity of subgraph isomorphism for classes of partial k-trees. Theoretical Computer Science\u00a0164, 287\u2013298 (1996)","journal-title":"Theoretical Computer Science"},{"key":"12_CR80","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"86","DOI":"10.1007\/3-540-45643-0_7","volume-title":"Algorithm Engineering and Experiments","author":"J. Gustedt","year":"2002","unstructured":"Gustedt, J., M\u00e6hle, O.A., Telle, J.A.: The Treewidth of Java Programs. In: Mount, D.M., Stein, C. (eds.) ALENEX 2002. LNCS, vol.\u00a02409, pp. 86\u201397. Springer, Heidelberg (2002)"},{"key":"12_CR81","doi-asserted-by":"publisher","first-page":"292","DOI":"10.1007\/s004530010021","volume":"27","author":"T. Hagerup","year":"2000","unstructured":"Hagerup, T.: Dynamic algorithms for graphs of bounded treewidth. Algorithmica\u00a027, 292\u2013315 (2000)","journal-title":"Algorithmica"},{"key":"12_CR82","doi-asserted-by":"publisher","first-page":"366","DOI":"10.1006\/jcss.1998.1592","volume":"57","author":"T. Hagerup","year":"1998","unstructured":"Hagerup, T., Katajainen, J., Nishimura, N., Ragde, P.: Characterizing multiterminal flow networks and computing flows in networks of small treewidth. Journal of Computer and System Sciences\u00a057, 366\u2013375 (1998)","journal-title":"Journal of Computer and System Sciences"},{"key":"12_CR83","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"218","DOI":"10.1007\/978-3-642-20662-7_19","volume-title":"Experimental Algorithms","author":"A. Hein","year":"2011","unstructured":"Hein, A., Koster, A.M.C.A.: An Experimental Evaluation of Treewidth at Most Four Reductions. In: Pardalos, P.M., Rebennack, S. (eds.) SEA 2011. LNCS, vol.\u00a06630, pp. 218\u2013229. Springer, Heidelberg (2011)"},{"key":"12_CR84","doi-asserted-by":"publisher","first-page":"367","DOI":"10.1006\/jcss.2000.1727","volume":"62","author":"R. Impagliazzo","year":"2001","unstructured":"Impagliazzo, R., Paturi, R.: On the complexity of k-SAT. Journal of Computer and System Sciences\u00a062, 367\u2013375 (2001)","journal-title":"Journal of Computer and System Sciences"},{"key":"12_CR85","doi-asserted-by":"publisher","first-page":"171","DOI":"10.1142\/S0129054199000137","volume":"10","author":"S. Isobe","year":"1999","unstructured":"Isobe, S., Zhou, X., Nishizeki, T.: A polynomial-time algorithm for finding total colorings of partial k-trees. International Journal of Foundations of Computer Science\u00a010, 171\u2013194 (1999)","journal-title":"International Journal of Foundations of Computer Science"},{"key":"12_CR86","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"805","DOI":"10.1007\/3-540-63165-8_233","volume-title":"Automata, Languages and Programming","author":"V. Kabanets","year":"1997","unstructured":"Kabanets, V.: Recognizability Equals Definability for Partial k-Paths. In: Degano, P., Gorrieri, R., Marchetti-Spaccamela, A. (eds.) ICALP 1997. LNCS, vol.\u00a01256, pp. 805\u2013815. Springer, Heidelberg (1997)"},{"key":"12_CR87","doi-asserted-by":"publisher","first-page":"348","DOI":"10.1007\/s004530010024","volume":"27","author":"D. Kaller","year":"2000","unstructured":"Kaller, D.: Definability equals recognizability of partial 3-trees and k-connected partial k-trees. Algorithmica\u00a027, 348\u2013381 (2000)","journal-title":"Algorithmica"},{"key":"12_CR88","doi-asserted-by":"publisher","first-page":"407","DOI":"10.1016\/S0304-3975(99)00240-6","volume":"240","author":"M.A. Kashem","year":"2000","unstructured":"Kashem, M.A., Zhou, X., Nishizeki, T.: Algorithms for generalized vertex-rankings of partial k-trees. Theoretical Computer Science\u00a0240, 407\u2013427 (2000)","journal-title":"Theoretical Computer Science"},{"key":"12_CR89","doi-asserted-by":"publisher","first-page":"345","DOI":"10.1016\/0020-0190(92)90234-M","volume":"42","author":"N.G. Kinnersley","year":"1992","unstructured":"Kinnersley, N.G.: The vertex separation number of a graph equals its path width. Information Processing Letters\u00a042, 345\u2013350 (1992)","journal-title":"Information Processing Letters"},{"key":"12_CR90","volume-title":"Algorithm Design","author":"J. Kleinberg","year":"2005","unstructured":"Kleinberg, J., Tardos, E.: Algorithm Design. Addison-Wesley, Boston (2005)"},{"key":"12_CR91","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","DOI":"10.1007\/BFb0045375","volume-title":"Treewidth","author":"T. Kloks","year":"1994","unstructured":"Kloks, T.: Treewidth. Computations and Approximations. LNCS, vol.\u00a0842. Springer, Heidelberg (1994)"},{"issue":"4","key":"12_CR92","doi-asserted-by":"publisher","first-page":"568","DOI":"10.1016\/j.disopt.2011.06.001","volume":"8","author":"J. Kneis","year":"2011","unstructured":"Kneis, J., Langer, A., Rossmanith, P.: Courcelle\u2019s theorem - a game-theoretic approach. Discrete Optimization\u00a08(4), 568\u2013594 (2011)","journal-title":"Discrete Optimization"},{"key":"12_CR93","unstructured":"Kneis, J., M\u00f6lle, D., Richter, S., Rossmanith, P.: A bound on the pathwidth of sparse graphs with applications to exact algorithms 23, 407\u2013427 (2009)"},{"issue":"3","key":"12_CR94","doi-asserted-by":"publisher","first-page":"170","DOI":"10.1002\/net.10046","volume":"40","author":"A.M.C.A. Koster","year":"2002","unstructured":"Koster, A.M.C.A., van Hoesel, S.P.M., Kolen, A.W.J.: Solving partial constraint satisfaction problems with tree decomposition. Networks\u00a040(3), 170\u2013180 (2002)","journal-title":"Networks"},{"key":"12_CR95","doi-asserted-by":"publisher","first-page":"987","DOI":"10.1007\/s00453-010-9390-4","volume":"60","author":"A. Koutsonas","year":"2011","unstructured":"Koutsonas, A., Thilikos, D.M.: Planar feedback vertex set and face cover: combinatorial bounds and subexponential algorithms. Algorithmica\u00a060, 987\u20131003 (2011)","journal-title":"Algorithmica"},{"key":"12_CR96","doi-asserted-by":"publisher","first-page":"20","DOI":"10.1006\/jagm.1996.0002","volume":"20","author":"J. Lagergren","year":"1996","unstructured":"Lagergren, J.: Efficient parallel algorithms for graphs of bounded tree-width. Journal of Algorithms\u00a020, 20\u201344 (1996)","journal-title":"Journal of Algorithms"},{"key":"12_CR97","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"532","DOI":"10.1007\/3-540-54233-7_161","volume-title":"Automata, Languages and Programming","author":"J. Lagergren","year":"1991","unstructured":"Lagergren, J., Arnborg, S.: Finding Minimal Forbidden Minors Using a Finite Congruence. In: Albert, J.L., Monien, B., Rodr\u00edguez-Artalejo, M. (eds.) ICALP 1991. LNCS, vol.\u00a0510, pp. 532\u2013543. Springer, Heidelberg (1991)"},{"key":"12_CR98","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"618","DOI":"10.1007\/BFb0028596","volume-title":"STACS 98","author":"D. Lapoire","year":"1998","unstructured":"Lapoire, D.: Recognizability Equals Definability, for Every Set of Graphs of Bounded Tree-width. In: Meinel, C., Morvan, M. (eds.) STACS 1998. LNCS, vol.\u00a01373, pp. 618\u2013628. Springer, Heidelberg (1998)"},{"key":"12_CR99","doi-asserted-by":"crossref","first-page":"157","DOI":"10.1111\/j.2517-6161.1988.tb01721.x","volume":"50","author":"S.J. Lauritzen","year":"1988","unstructured":"Lauritzen, S.J., Spiegelhalter, D.J.: Local computations with probabilities on graphical structures and their application to expert systems. The Journal of the Royal Statistical Society, Series B (Methodological)\u00a050, 157\u2013224 (1988)","journal-title":"The Journal of the Royal Statistical Society, Series B (Methodological)"},{"key":"12_CR100","unstructured":"Leaver-Fay, A., Liu, Y., Snoeyink, J.: Faster placement of hydrogen atoms in protein structures by dynamic programming. In: Proceedings of the 6th Workshop on Algorithm Engineering and Experimentation and the 1st Workshop on Analytic Algorithmics and Combinatorics, ALENEX\/ANALCO 2004, pp. 39\u201348 (2004)"},{"key":"12_CR101","doi-asserted-by":"publisher","first-page":"465","DOI":"10.1007\/BF00264496","volume":"16","author":"T. Lengauer","year":"1981","unstructured":"Lengauer, T.: Black-white pebbles and graph separation. Acta Informatica\u00a016, 465\u2013475 (1981)","journal-title":"Acta Informatica"},{"key":"12_CR102","doi-asserted-by":"publisher","first-page":"177","DOI":"10.1137\/0136016","volume":"36","author":"R.J. Lipton","year":"1979","unstructured":"Lipton, R.J., Tarjan, R.E.: A separator theorem for planar graphs. SIAM Journal on Applied Mathematics\u00a036, 177\u2013189 (1979)","journal-title":"SIAM Journal on Applied Mathematics"},{"key":"12_CR103","doi-asserted-by":"publisher","first-page":"615","DOI":"10.1137\/0209046","volume":"9","author":"R.J. Lipton","year":"1980","unstructured":"Lipton, R.J., Tarjan, R.E.: Applications of a planar separator theorem. SIAM Journal on Computing\u00a09, 615\u2013627 (1980)","journal-title":"SIAM Journal on Computing"},{"key":"12_CR104","doi-asserted-by":"crossref","unstructured":"Lokshtanov, D., Marx, D., Saurabh, S.: Known algorithms on graphs on bounded treewidth are probably optimal. In: Randall, D. (ed.) Proceedings of the 21st Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2011, pp. 777\u2013789 (2011)","DOI":"10.1137\/1.9781611973082.61"},{"key":"12_CR105","doi-asserted-by":"publisher","first-page":"276","DOI":"10.1016\/j.dam.2004.01.016","volume":"145","author":"J.A. Makowsky","year":"2004","unstructured":"Makowsky, J.A.: Coloured Tutte polynomials and Kauffman brackets for graphs of bounded tree width. Discrete Applied Mathematics\u00a0145, 276\u2013290 (2004)","journal-title":"Discrete Applied Mathematics"},{"key":"12_CR106","doi-asserted-by":"publisher","first-page":"321","DOI":"10.1002\/net.3230210305","volume":"21","author":"E. Mata-Montero","year":"1991","unstructured":"Mata-Montero, E.: Resilience of partial k-tree networks with edge and node failures. Networks\u00a021, 321\u2013344 (1991)","journal-title":"Networks"},{"key":"12_CR107","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1016\/0196-6774(91)90020-Y","volume":"12","author":"J. Matou\u0161ek","year":"1991","unstructured":"Matou\u0161ek, J., Thomas, R.: Algorithms for finding tree-decompositions of graphs. Journal of Algorithms\u00a012, 1\u201322 (1991)","journal-title":"Journal of Algorithms"},{"key":"12_CR108","doi-asserted-by":"publisher","first-page":"183","DOI":"10.1016\/S0012-365X(03)00236-X","volume":"273","author":"C. McDiarmid","year":"2003","unstructured":"McDiarmid, C., Reed, B.: Channel assignment on graphs of bounded treewidth. Discrete Mathematics\u00a0273, 183\u2013192 (2003)","journal-title":"Discrete Mathematics"},{"key":"12_CR109","first-page":"221","volume-title":"Proceedings of the 24th Annual Symposium on Theory of Computing, STOC 1992","author":"B. Reed","year":"1992","unstructured":"Reed, B.: Finding approximate separators and computing tree-width quickly. In: Proceedings of the 24th Annual Symposium on Theory of Computing, STOC 1992, pp. 221\u2013228. ACM Press, New York (1992)"},{"key":"12_CR110","doi-asserted-by":"publisher","first-page":"39","DOI":"10.1016\/0095-8956(83)90079-5","volume":"35","author":"N. Robertson","year":"1983","unstructured":"Robertson, N., Seymour, P.D.: Graph minors. I. Excluding a forest. Journal of Combinatorial Theory, Series B\u00a035, 39\u201361 (1983)","journal-title":"Journal of Combinatorial Theory, Series B"},{"key":"12_CR111","doi-asserted-by":"publisher","first-page":"49","DOI":"10.1016\/0095-8956(84)90013-3","volume":"36","author":"N. Robertson","year":"1984","unstructured":"Robertson, N., Seymour, P.D.: Graph minors. III. Planar tree-width. Journal of Combinatorial Theory, Series B\u00a036, 49\u201364 (1984)","journal-title":"Journal of Combinatorial Theory, Series B"},{"key":"12_CR112","doi-asserted-by":"crossref","unstructured":"Robertson, N., Seymour, P.D.: Graph minors \u2014 a survey. In: Anderson, I. (ed.) Surveys in Combinatorics, pp. 153\u2013171. Cambridge Univ. Press (1985)","DOI":"10.1017\/CBO9781107325678.009"},{"key":"12_CR113","doi-asserted-by":"publisher","first-page":"309","DOI":"10.1016\/0196-6774(86)90023-4","volume":"7","author":"N. Robertson","year":"1986","unstructured":"Robertson, N., Seymour, P.D.: Graph minors. II. Algorithmic aspects of tree-width. Journal of Algorithms\u00a07, 309\u2013322 (1986)","journal-title":"Journal of Algorithms"},{"key":"12_CR114","doi-asserted-by":"publisher","first-page":"92","DOI":"10.1016\/0095-8956(86)90030-4","volume":"41","author":"N. Robertson","year":"1986","unstructured":"Robertson, N., Seymour, P.D.: Graph minors. V. Excluding a planar graph. Journal of Combinatorial Theory, Series B\u00a041, 92\u2013114 (1986)","journal-title":"Journal of Combinatorial Theory, Series B"},{"key":"12_CR115","doi-asserted-by":"publisher","first-page":"115","DOI":"10.1016\/0095-8956(86)90031-6","volume":"41","author":"N. Robertson","year":"1986","unstructured":"Robertson, N., Seymour, P.D.: Graph minors. VI. Disjoint paths across a disc. Journal of Combinatorial Theory, Series B\u00a041, 115\u2013138 (1986)","journal-title":"Journal of Combinatorial Theory, Series B"},{"key":"12_CR116","doi-asserted-by":"publisher","first-page":"212","DOI":"10.1016\/0095-8956(88)90070-6","volume":"45","author":"N. Robertson","year":"1988","unstructured":"Robertson, N., Seymour, P.D.: Graph minors. VII. Disjoint paths on a surface. Journal of Combinatorial Theory, Series B\u00a045, 212\u2013254 (1988)","journal-title":"Journal of Combinatorial Theory, Series B"},{"key":"12_CR117","doi-asserted-by":"publisher","first-page":"227","DOI":"10.1016\/0095-8956(90)90120-O","volume":"48","author":"N. Robertson","year":"1990","unstructured":"Robertson, N., Seymour, P.D.: Graph minors. IV. Tree-width and well-quasi-ordering. Journal of Combinatorial Theory, Series B\u00a048, 227\u2013254 (1990)","journal-title":"Journal of Combinatorial Theory, Series B"},{"key":"12_CR118","doi-asserted-by":"publisher","first-page":"40","DOI":"10.1016\/0095-8956(90)90063-6","volume":"49","author":"N. Robertson","year":"1990","unstructured":"Robertson, N., Seymour, P.D.: Graph minors. IX. Disjoint crossed paths. Journal of Combinatorial Theory, Series B\u00a049, 40\u201377 (1990)","journal-title":"Journal of Combinatorial Theory, Series B"},{"key":"12_CR119","doi-asserted-by":"publisher","first-page":"255","DOI":"10.1016\/0095-8956(90)90121-F","volume":"48","author":"N. Robertson","year":"1990","unstructured":"Robertson, N., Seymour, P.D.: Graph minors. VIII. A Kuratowski theorem for general surfaces. Journal of Combinatorial Theory, Series B\u00a048, 255\u2013288 (1990)","journal-title":"Journal of Combinatorial Theory, Series B"},{"key":"12_CR120","doi-asserted-by":"publisher","first-page":"153","DOI":"10.1016\/0095-8956(91)90061-N","volume":"52","author":"N. Robertson","year":"1991","unstructured":"Robertson, N., Seymour, P.D.: Graph minors. X. Obstructions to tree-decomposition. Journal of Combinatorial Theory, Series B\u00a052, 153\u2013190 (1991)","journal-title":"Journal of Combinatorial Theory, Series B"},{"key":"12_CR121","unstructured":"Robertson, N., Seymour, P.D.: Graph minors. XXII. Irrelevant vertices in linkage problems (1992) (manuscript)"},{"key":"12_CR122","doi-asserted-by":"publisher","first-page":"72","DOI":"10.1006\/jctb.1994.1007","volume":"60","author":"N. Robertson","year":"1994","unstructured":"Robertson, N., Seymour, P.D.: Graph minors. XI. Distance on a surface. Journal of Combinatorial Theory, Series B\u00a060, 72\u2013106 (1994)","journal-title":"Journal of Combinatorial Theory, Series B"},{"key":"12_CR123","doi-asserted-by":"publisher","first-page":"240","DOI":"10.1006\/jctb.1995.1034","volume":"64","author":"N. Robertson","year":"1995","unstructured":"Robertson, N., Seymour, P.D.: Graph minors. XII. Excluding a non-planar graph. Journal of Combinatorial Theory, Series B\u00a064, 240\u2013272 (1995)","journal-title":"Journal of Combinatorial Theory, Series B"},{"key":"12_CR124","doi-asserted-by":"publisher","first-page":"65","DOI":"10.1006\/jctb.1995.1006","volume":"63","author":"N. Robertson","year":"1995","unstructured":"Robertson, N., Seymour, P.D.: Graph minors. XIII. The disjoint paths problem. Journal of Combinatorial Theory, Series B\u00a063, 65\u2013110 (1995)","journal-title":"Journal of Combinatorial Theory, Series B"},{"key":"12_CR125","doi-asserted-by":"publisher","first-page":"23","DOI":"10.1006\/jctb.1995.1042","volume":"65","author":"N. Robertson","year":"1995","unstructured":"Robertson, N., Seymour, P.D.: Graph minors. XIV. Extending an embedding. Journal of Combinatorial Theory, Series B\u00a065, 23\u201350 (1995)","journal-title":"Journal of Combinatorial Theory, Series B"},{"key":"12_CR126","doi-asserted-by":"publisher","first-page":"112","DOI":"10.1006\/jctb.1996.0059","volume":"68","author":"N. Robertson","year":"1996","unstructured":"Robertson, N., Seymour, P.D.: Graph minors. XV. Giant steps. Journal of Combinatorial Theory, Series B\u00a068, 112\u2013148 (1996)","journal-title":"Journal of Combinatorial Theory, Series B"},{"key":"12_CR127","doi-asserted-by":"publisher","first-page":"162","DOI":"10.1006\/jctb.1999.1919","volume":"77","author":"N. Robertson","year":"1999","unstructured":"Robertson, N., Seymour, P.D.: Graph minors. XVII. Taming a vortex. Journal of Combinatorial Theory, Series B\u00a077, 162\u2013210 (1999)","journal-title":"Journal of Combinatorial Theory, Series B"},{"key":"12_CR128","doi-asserted-by":"publisher","first-page":"43","DOI":"10.1016\/S0095-8956(03)00042-X","volume":"89","author":"N. Robertson","year":"2003","unstructured":"Robertson, N., Seymour, P.D.: Graph minors. XVI. Excluding a non-planar graph. Journal of Combinatorial Theory, Series B\u00a089, 43\u201376 (2003)","journal-title":"Journal of Combinatorial Theory, Series B"},{"key":"12_CR129","doi-asserted-by":"publisher","first-page":"77","DOI":"10.1016\/S0095-8956(03)00067-4","volume":"89","author":"N. Robertson","year":"2003","unstructured":"Robertson, N., Seymour, P.D.: Graph minors. XVIII. Tree-decompositions and well-quasi ordering. Journal of Combinatorial Theory, Series B\u00a089, 77\u2013108 (2003)","journal-title":"Journal of Combinatorial Theory, Series B"},{"key":"12_CR130","doi-asserted-by":"publisher","first-page":"325","DOI":"10.1016\/j.jctb.2003.08.005","volume":"90","author":"N. Robertson","year":"2004","unstructured":"Robertson, N., Seymour, P.D.: Graph minors. XIX. Well-quasi-ordering on a surface. Journal of Combinatorial Theory, Series B\u00a090, 325\u2013385 (2004)","journal-title":"Journal of Combinatorial Theory, Series B"},{"key":"12_CR131","doi-asserted-by":"publisher","first-page":"325","DOI":"10.1016\/j.jctb.2004.08.001","volume":"92","author":"N. Robertson","year":"2004","unstructured":"Robertson, N., Seymour, P.D.: Graph minors. XX. Wagner\u2019s conjecture. Journal of Combinatorial Theory, Series B\u00a092, 325\u2013357 (2004)","journal-title":"Journal of Combinatorial Theory, Series B"},{"key":"12_CR132","doi-asserted-by":"publisher","first-page":"583","DOI":"10.1016\/j.jctb.2008.08.003","volume":"99","author":"N. Robertson","year":"2009","unstructured":"Robertson, N., Seymour, P.D.: Graph minors. XXI. Graphs with unique linkages. Journal of Combinatorial Theory, Series B\u00a099, 583\u2013616 (2009)","journal-title":"Journal of Combinatorial Theory, Series B"},{"key":"12_CR133","doi-asserted-by":"publisher","first-page":"181","DOI":"10.1016\/j.jctb.2009.07.003","volume":"100","author":"N. Robertson","year":"2010","unstructured":"Robertson, N., Seymour, P.D.: Graph minors XXIII. Nash-Williams\u2019 immersion conjecture. Journal of Combinatorial Theory, Series B\u00a0100, 181\u2013205 (2010)","journal-title":"Journal of Combinatorial Theory, Series B"},{"key":"12_CR134","doi-asserted-by":"publisher","first-page":"323","DOI":"10.1006\/jctb.1994.1073","volume":"62","author":"N. Robertson","year":"1994","unstructured":"Robertson, N., Seymour, P.D., Thomas, R.: Quickly excluding a planar graph. Journal of Combinatorial Theory, Series B\u00a062, 323\u2013348 (1994)","journal-title":"Journal of Combinatorial Theory, Series B"},{"issue":"1","key":"12_CR135","doi-asserted-by":"publisher","first-page":"101","DOI":"10.1137\/S0895480193243043","volume":"9","author":"D.P. Sanders","year":"1996","unstructured":"Sanders, D.P.: On linear recognition of tree-width at most four. SIAM Journal on Discrete Mathematics\u00a09(1), 101\u2013117 (1996)","journal-title":"SIAM Journal on Discrete Mathematics"},{"key":"12_CR136","doi-asserted-by":"publisher","first-page":"330","DOI":"10.1016\/j.jda.2010.02.002","volume":"8","author":"I. Sau","year":"2010","unstructured":"Sau, I., Thilikos, D.M.: Subexponential parameterized algorithms for degree-constrained subgraph problems on planar graphs. Journal of Discrete Algorithms\u00a08, 330\u2013338 (2010)","journal-title":"Journal of Discrete Algorithms"},{"issue":"2","key":"12_CR137","doi-asserted-by":"publisher","first-page":"217","DOI":"10.1007\/BF01215352","volume":"14","author":"P.D. Seymour","year":"1994","unstructured":"Seymour, P.D., Thomas, R.: Call routing and the ratcatcher. Combinatorica\u00a014(2), 217\u2013241 (1994)","journal-title":"Combinatorica"},{"key":"12_CR138","doi-asserted-by":"publisher","first-page":"529","DOI":"10.1137\/S0895480194275825","volume":"10","author":"J.A. Telle","year":"1997","unstructured":"Telle, J.A., Proskurowski, A.: Algorithms for vertex partitioning problems on partial k-trees. SIAM Journal on Discrete Mathematics\u00a010, 529\u2013550 (1997)","journal-title":"SIAM Journal on Discrete Mathematics"},{"key":"12_CR139","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1016\/j.jalgor.2004.12.001","volume":"56","author":"D.M. Thilikos","year":"2005","unstructured":"Thilikos, D.M., Serna, M.J., Bodlaender, H.L.: Cutwidth I: A linear time fixed parameter algorithm. Journal of Algorithms\u00a056, 1\u201324 (2005)","journal-title":"Journal of Algorithms"},{"key":"12_CR140","doi-asserted-by":"publisher","first-page":"25","DOI":"10.1016\/j.jalgor.2004.12.003","volume":"56","author":"D.M. Thilikos","year":"2005","unstructured":"Thilikos, D.M., Serna, M.J., Bodlaender, H.L.: Cutwidth II: Algorithms for partial w-trees of bounded degree. Journal of Algorithms\u00a056, 25\u201349 (2005)","journal-title":"Journal of Algorithms"},{"key":"12_CR141","unstructured":"van Rooij, J.M.M.: Exact exponential-time algorithms for domination problems in graphs. PhD thesis, Department of Computer Science, Utrecht University (2011)"},{"key":"12_CR142","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"566","DOI":"10.1007\/978-3-642-04128-0_51","volume-title":"Algorithms - ESA 2009","author":"J.M.M. Rooij van","year":"2009","unstructured":"van Rooij, J.M.M., Bodlaender, H.L., Rossmanith, P.: Dynamic Programming on Tree Decompositions Using Generalised Fast Subset Convolution. In: Fiat, A., Sanders, P. (eds.) ESA 2009. LNCS, vol.\u00a05757, pp. 566\u2013577. Springer, Heidelberg (2009)"},{"key":"12_CR143","unstructured":"Wimer, T.V.: Linear Algorithms on k-Terminal Graphs. PhD thesis, Dept. of Computer Science, Clemson University (1987)"},{"key":"12_CR144","first-page":"43","volume":"50","author":"T.V. Wimer","year":"1985","unstructured":"Wimer, T.V., Hedetniemi, S.T., Laskar, R.: A methodology for constructing linear graph algorithms. Congressus Numerantium\u00a050, 43\u201360 (1985)","journal-title":"Congressus Numerantium"},{"key":"12_CR145","doi-asserted-by":"publisher","first-page":"227","DOI":"10.1007\/s004530010017","volume":"27","author":"X. Zhou","year":"2000","unstructured":"Zhou, X., Fuse, K., Nishizeki, T.: A linear algorithm for finding [g,f]-colorings of partial k-trees. Algorithmica\u00a027, 227\u2013243 (2000)","journal-title":"Algorithmica"}],"container-title":["Lecture Notes in Computer Science","The Multivariate Algorithmic Revolution and Beyond"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-642-30891-8_12","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,5,19]],"date-time":"2019-05-19T20:32:23Z","timestamp":1558297943000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-642-30891-8_12"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2012]]},"ISBN":["9783642308901","9783642308918"],"references-count":145,"URL":"https:\/\/doi.org\/10.1007\/978-3-642-30891-8_12","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"value":"0302-9743","type":"print"},{"value":"1611-3349","type":"electronic"}],"subject":[],"published":{"date-parts":[[2012]]}}}