{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,9,28]],"date-time":"2025-09-28T12:50:08Z","timestamp":1759063808658},"reference-count":46,"publisher":"Springer Science and Business Media LLC","issue":"1","license":[{"start":{"date-parts":[[2011,7,14]],"date-time":"2011-07-14T00:00:00Z","timestamp":1310601600000},"content-version":"tdm","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Algorithmica"],"published-print":{"date-parts":[[2012,9]]},"DOI":"10.1007\/s00453-011-9545-y","type":"journal-article","created":{"date-parts":[[2011,7,13]],"date-time":"2011-07-13T12:07:16Z","timestamp":1310558836000},"page":"3-18","source":"Crossref","is-referenced-by-count":9,"title":["Well Quasi Orders in Subclasses of Bounded Treewidth Graphs and Their Algorithmic Applications"],"prefix":"10.1007","volume":"64","author":[{"given":"Michael R.","family":"Fellows","sequence":"first","affiliation":[]},{"given":"Danny","family":"Hermelin","sequence":"additional","affiliation":[]},{"given":"Frances A.","family":"Rosamond","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2011,7,14]]},"reference":[{"key":"9545_CR1","first-page":"641","volume-title":"Proc. of the 19th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA)","author":"I. Adler","year":"2008","unstructured":"Adler, I., Grohe, M., Kreutzer, S.: Computing excluded minors. In: Proc. of the 19th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), pp. 641\u2013650 (2008)"},{"key":"9545_CR2","first-page":"322","volume-title":"Proc. of the 12th Scandinavian Symposium and Workshops on Algorithm Theory (SWAT)","author":"I. Adler","year":"2010","unstructured":"Adler, I., Dorn, F., Fomin, F.V., Sau, I., Thilikos, D.M.: Faster parameterized algorithms for minor containment. In: Proc. of the 12th Scandinavian Symposium and Workshops on Algorithm Theory (SWAT), pp. 322\u2013333 (2010)"},{"issue":"1","key":"9545_CR3","doi-asserted-by":"crossref","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. A survey. BIT Numer. Math. 25(1), 2\u201323 (1985)","journal-title":"BIT Numer. Math."},{"key":"9545_CR4","doi-asserted-by":"crossref","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 Appl. Math. 23, 11\u201324 (1989)","journal-title":"Discrete Appl. Math."},{"issue":"1\u20132","key":"9545_CR5","doi-asserted-by":"crossref","first-page":"3","DOI":"10.1016\/S0925-7721(97)00014-X","volume":"9","author":"H. Breu","year":"1998","unstructured":"Breu, H., Kirkpatrick, G.: Unit disk graph recognition is NP-hard. Comput. Geom. 9(1\u20132), 3\u201324 (1998)","journal-title":"Comput. Geom."},{"issue":"4","key":"9545_CR6","doi-asserted-by":"crossref","first-page":"535","DOI":"10.1137\/0608044","volume":"8","author":"D.G. Corneil","year":"1987","unstructured":"Corneil, D.G., Keil, J.M.: A dynamic programming approach to the dominating set problem on k-trees. SIAM J. Algebr. Discrete Methods 8(4), 535\u2013543 (1987)","journal-title":"SIAM J. Algebr. Discrete Methods"},{"issue":"1","key":"9545_CR7","doi-asserted-by":"crossref","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\u00a0I. Recognizable sets of finite graphs. Inf. Comput. 85(1), 12\u201375 (1990)","journal-title":"Inf. Comput."},{"issue":"4","key":"9545_CR8","doi-asserted-by":"crossref","first-page":"427","DOI":"10.1002\/jgt.3190140406","volume":"14","author":"P. Damaschke","year":"1990","unstructured":"Damaschke, P.: Induced subgraphs and well-quasi-ordering. J. Graph Theory 14(4), 427\u2013435 (1990)","journal-title":"J. Graph Theory"},{"key":"9545_CR9","first-page":"590","volume-title":"Proc. of the 16th ACM-SIAM Symposium on Discrete Algorithms (SODA)","author":"E. Demaine","year":"2005","unstructured":"Demaine, E., Hajiaghayi, M.T.: Bidimensionality: new connections between FPT algorithms and PTASs. In: Proc. of the 16th ACM-SIAM Symposium on Discrete Algorithms (SODA), pp. 590\u2013601 (2005)"},{"issue":"5","key":"9545_CR10","doi-asserted-by":"crossref","first-page":"489","DOI":"10.1002\/jgt.3190160509","volume":"16","author":"G. Ding","year":"1992","unstructured":"Ding, G.: Subgraphs and well-quasi-ordering. J. Graph Theory 16(5), 489\u2013502 (1992)","journal-title":"J. Graph Theory"},{"key":"9545_CR11","doi-asserted-by":"crossref","DOI":"10.1007\/978-1-4612-0515-9","volume-title":"Parameterized Complexity","author":"R. Downey","year":"1999","unstructured":"Downey, R., Fellows, M.: Parameterized Complexity. Springer, Berlin (1999)"},{"issue":"3","key":"9545_CR12","doi-asserted-by":"crossref","first-page":"1","DOI":"10.7155\/jgaa.00014","volume":"3","author":"D. Eppstein","year":"1999","unstructured":"Eppstein, D.: Subgraph isomorphism in planar graphs and related problems. J. Graph Algorithms Appl. 3(3), 1\u201327 (1999)","journal-title":"J. Graph Algorithms Appl."},{"key":"9545_CR13","doi-asserted-by":"crossref","first-page":"2","DOI":"10.1007\/978-3-642-10217-2_2","volume-title":"Proc. of the 20th International Workshop On Combinatorial Algorithms (IWOCA)","author":"M.R. Fellows","year":"2009","unstructured":"Fellows, M.R.: Towards fully multivariate algorithmics: some new results and directions in parameter ecology. In: Proc. of the 20th International Workshop On Combinatorial Algorithms (IWOCA), pp. 2\u201310 (2009)"},{"key":"9545_CR14","doi-asserted-by":"crossref","first-page":"143","DOI":"10.1016\/j.ic.2010.11.026","volume":"209","author":"M.R. Fellows","year":"2011","unstructured":"Fellows, M.R., Fomin, F.V., Lokshtanov, D., Rosamond, F.A., Saurabh, S., Szeider, S., Thomassen,\u00a0C.: On the complexity of some colorful problems parameterized by treewidth. Inf. Comput. 209, 143\u2013153 (2011)","journal-title":"Inf. Comput."},{"issue":"3","key":"9545_CR15","doi-asserted-by":"crossref","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. J. ACM 35(3), 727\u2013739 (1988)","journal-title":"J. ACM"},{"issue":"1","key":"9545_CR16","doi-asserted-by":"crossref","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 J. Discrete Math. 5(1), 117\u2013126 (1992)","journal-title":"SIAM J. Discrete Math."},{"key":"9545_CR17","first-page":"294","volume-title":"Proc. of the 19th International Symposium on Algorithms and Computation (ISAAC)","author":"M.R. Fellows","year":"2008","unstructured":"Fellows, M.R., Lokshtanov, D., Misra, N., Rosamond, F.A., Saurabh, S.: Graph layout problems parameterized by vertex cover. In: Proc. of the 19th International Symposium on Algorithms and Computation (ISAAC), pp. 294\u2013305 (2008)"},{"key":"9545_CR18","volume-title":"Parameterized Complexity Theory","author":"J. Flum","year":"2006","unstructured":"Flum, J., Grohe, M.: Parameterized Complexity Theory. Springer, Berlin (2006)"},{"key":"9545_CR19","doi-asserted-by":"crossref","first-page":"503","DOI":"10.1137\/1.9781611973075.43","volume-title":"Proc. of the 21st ACM-SIAM Symposium on Discrete Algorithms (SODA)","author":"F.V. Fomin","year":"2010","unstructured":"Fomin, F.V., Lokshtanov, D., Raman, V., Saurabh, S.: Bidimensionality and EPTAS. In: Proc. of the 21st ACM-SIAM Symposium on Discrete Algorithms (SODA), pp. 503\u2013510 (2010)"},{"issue":"4","key":"9545_CR20","doi-asserted-by":"crossref","first-page":"373","DOI":"10.1007\/s00224-004-1178-y","volume":"38","author":"J. Gramm","year":"2005","unstructured":"Gramm, J., Guo, J., H\u00fcffner, F., Niedermeier, R.: Graph-modeled data clustering: exact algorithms for clique generation. Theory Comput. Syst. 38(4), 373\u2013392 (2005)","journal-title":"Theory Comput. Syst."},{"issue":"7","key":"9545_CR21","doi-asserted-by":"crossref","first-page":"326","DOI":"10.1112\/plms\/s3-2.1.326","volume":"2","author":"G. Higman","year":"1952","unstructured":"Higman, G.: Ordering by divisibility in abstract algebras. Proc. Lond. Math. Soc. III 2(7), 326\u2013336 (1952)","journal-title":"Proc. Lond. Math. Soc. III"},{"key":"9545_CR22","first-page":"177","volume-title":"Proc. of the 28th International Symposium on Theoretical Aspects of Computer Science (STACS)","author":"B.M.P. Jansen","year":"2011","unstructured":"Jansen, B.M.P., Bodlaender, H.L.: Vertex cover kernelization revisited: upper and lower bounds for a refined parameter. In: Proc. of the 28th International Symposium on Theoretical Aspects of Computer Science (STACS), pp. 177\u2013188 (2011)"},{"issue":"1\u20133","key":"9545_CR23","doi-asserted-by":"crossref","first-page":"117","DOI":"10.1016\/S0166-218X(01)00220-7","volume":"115","author":"T. Kloks","year":"2001","unstructured":"Kloks, T., Tan, R.B.: Bandwidth and topological bandwidth of graphs with few\u00a0P 4\u2019s. Discrete Appl. Math. 115(1\u20133), 117\u2013133 (2001)","journal-title":"Discrete Appl. Math."},{"issue":"1","key":"9545_CR24","doi-asserted-by":"crossref","first-page":"53","DOI":"10.1016\/0095-8956(91)90090-7","volume":"52","author":"J. Kratochv\u00edl","year":"1991","unstructured":"Kratochv\u00edl, J.: String graphs. I. The number of critical nonstring graphs is infinite. J. Comb. Theory, Ser. B 52(1), 53\u201366 (1991)","journal-title":"J. Comb. Theory, Ser. B"},{"issue":"1","key":"9545_CR25","doi-asserted-by":"crossref","first-page":"67","DOI":"10.1016\/0095-8956(91)90091-W","volume":"52","author":"J. Kratochv\u00edl","year":"1991","unstructured":"Kratochv\u00edl, J.: String graphs. II. Recognizing string graphs is NP-hard. J. Comb. Theory, Ser. B 52(1), 67\u201378 (1991)","journal-title":"J. Comb. Theory, Ser. B"},{"key":"9545_CR26","doi-asserted-by":"crossref","unstructured":"Kratsch, S., Schweitzer, P.: Isomorphism for graphs of bounded feedback vertex set number. In: Proc. of the 12th Scandinavian Symposium and Workshops on Algorithm Theory (SWAT), pp. 81\u201392","DOI":"10.1007\/978-3-642-13731-0_9"},{"key":"9545_CR27","first-page":"210","volume":"95","author":"J.B. Kruskal","year":"1960","unstructured":"Kruskal, J.B.: Well-quasi-ordering, the tree theorem, and Vazsonyi\u2019s conjecture. Trans. Am. Math. Soc. 95, 210\u2013225 (1960)","journal-title":"Trans. Am. Math. Soc."},{"key":"9545_CR28","first-page":"549","volume-title":"Proc. of the 18th Annual European Symposium on Algorithms (ESA)","author":"M. Lampis","year":"2010","unstructured":"Lampis, M.: Algorithmic meta-theorems for restrictions of treewidth. In: Proc. of the 18th Annual European Symposium on Algorithms (ESA), pp. 549\u2013560 (2010)"},{"key":"9545_CR29","doi-asserted-by":"crossref","first-page":"105","DOI":"10.1016\/0095-8956(72)90015-9","volume":"12","author":"W. Mader","year":"1972","unstructured":"Mader, W.: Wohlquasigeordnete Klassen Endlicher Graphen. J. Comb. Theory, Ser. B 12, 105\u2013122 (1972)","journal-title":"J. Comb. Theory, Ser. B"},{"key":"9545_CR30","first-page":"317","volume-title":"Proc. of the 8th Colloquium on Trees in Algebra and Programming (CAAP)","author":"F. Makedon","year":"1983","unstructured":"Makedon, F., Papadimitriou, C.H., Sudborough, I.H.: Topological bandwidth. In: Proc. of the 8th Colloquium on Trees in Algebra and Programming (CAAP), pp. 317\u2013331 (1983)"},{"issue":"4","key":"9545_CR31","first-page":"703","volume":"29","author":"J. Matou\u0161ek","year":"1988","unstructured":"Matou\u0161ek, J., Ne\u0161et\u0159il, J., Thomas, R.D.: On polynomial time decidability of induced-minor-closed classes. Comment. Math. Univ. Carol. 29(4), 703\u2013710 (1988)","journal-title":"Comment. Math. Univ. Carol."},{"key":"9545_CR32","doi-asserted-by":"crossref","first-page":"96","DOI":"10.4064\/fm-10-1-96-115","volume":"10","author":"K. Menger","year":"1927","unstructured":"Menger, K.: Zur allgemeinen Kurventheorie. Fundam. Math. 10, 96\u2013115 (1927)","journal-title":"Fundam. Math."},{"issue":"5","key":"9545_CR33","doi-asserted-by":"crossref","first-page":"1018","DOI":"10.1137\/0217064","volume":"17","author":"Z. Miller","year":"1988","unstructured":"Miller, Z.: A linear algorithm for topological bandwidth in degree-three trees. SIAM J. Comput. 17(5), 1018\u20131035 (1988)","journal-title":"SIAM J. Comput."},{"key":"9545_CR34","doi-asserted-by":"crossref","first-page":"209","DOI":"10.1016\/0304-3975(88)90028-X","volume":"58","author":"B. Monien","year":"1988","unstructured":"Monien, B., Sudborough, I.H.: Min cut is NP-complete for edge weighted trees. Theor. Comput. Sci. 58, 209\u2013229 (1988)","journal-title":"Theor. Comput. Sci."},{"issue":"4","key":"9545_CR35","doi-asserted-by":"crossref","first-page":"833","DOI":"10.1017\/S0305004100003844","volume":"59","author":"C.S.J.A. Nash-Williams","year":"1963","unstructured":"Nash-Williams, C.S.J.A.: On well-quasi-ordering finite trees. Math. Proc. Camb. Philos. Soc. 59(4), 833\u2013835 (1963)","journal-title":"Math. Proc. Camb. Philos. Soc."},{"key":"9545_CR36","unstructured":"Niedermeier, R.: Reflections on multivariate algorithmics and problem parameterization. In: Proc. of the 27th International Symposium on Theoretical Aspects of Computer Science (STACS\u00a02010), pp. 17\u201332 (2010)"},{"key":"9545_CR37","doi-asserted-by":"crossref","DOI":"10.1093\/acprof:oso\/9780198566076.001.0001","volume-title":"Invitation to Fixed-Parameter Algorithms","author":"R. Niedermeier","year":"2006","unstructured":"Niedermeier, R.: Invitation to Fixed-Parameter Algorithms. Oxford University Press, London (2006)"},{"issue":"4","key":"9545_CR38","doi-asserted-by":"crossref","first-page":"593","DOI":"10.1007\/s00454-002-2891-4","volume":"28","author":"J. Pach","year":"2002","unstructured":"Pach, J., T\u00f3th, G.: Recognizing string graphs is decidable. Discrete Comput. Geom. 28(4), 593\u2013606 (2002)","journal-title":"Discrete Comput. Geom."},{"issue":"1\u20133","key":"9545_CR39","doi-asserted-by":"crossref","first-page":"375","DOI":"10.1016\/S0012-365X(01)00094-2","volume":"244","author":"M. Petkov\u0161ek","year":"2002","unstructured":"Petkov\u0161ek, M.: Letter graphs and well-quasi-order by induced subgraphs. Discrete Math. 244(1\u20133), 375\u2013388 (2002)","journal-title":"Discrete Math."},{"issue":"1","key":"9545_CR40","doi-asserted-by":"crossref","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. J. Comb. Theory, Ser. B 63(1), 65\u2013110 (1995)","journal-title":"J. Comb. Theory, Ser. B"},{"issue":"1","key":"9545_CR41","first-page":"325","volume":"92","author":"N. Robertson","year":"2004","unstructured":"Robertson, N., Seymour, P.D.: Graph minors. XX. Wagner\u2019s conjecture. J. Comb. Theory, Ser. B 92(1), 325\u2013357 (2004)","journal-title":"J. Comb. Theory, Ser. B"},{"issue":"2","key":"9545_CR42","doi-asserted-by":"crossref","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-William\u2019s immersion conjecture. J. Comb. Theory, Ser. B 100(2), 181\u2013205 (2010)","journal-title":"J. Comb. Theory, Ser. B"},{"issue":"2","key":"9545_CR43","doi-asserted-by":"crossref","first-page":"319","DOI":"10.1016\/j.jcss.2003.07.002","volume":"68","author":"M. Schaefer","year":"2004","unstructured":"Schaefer, M., Stefankovic, D.: Decidability of string graphs. J. Comput. Syst. Sci. 68(2), 319\u2013334 (2004)","journal-title":"J. Comput. Syst. Sci."},{"issue":"2","key":"9545_CR44","doi-asserted-by":"crossref","first-page":"365","DOI":"10.1016\/S0022-0000(03)00045-X","volume":"67","author":"M. Schaefer","year":"2003","unstructured":"Schaefer, M., Sedgwick, E., Stefankovic, D.: Recognizing string graphs in NP. J. Comput. Syst. Sci. 67(2), 365\u2013380 (2003)","journal-title":"J. Comput. Syst. Sci."},{"key":"9545_CR45","doi-asserted-by":"crossref","first-page":"240","DOI":"10.1016\/0095-8956(85)90069-3","volume":"38","author":"R.D. Thomas","year":"1985","unstructured":"Thomas, R.D.: Graphs without K 4 and well-quasi-ordering. J. Comb. Theory, Ser. B 38, 240\u2013247 (1985)","journal-title":"J. Comb. Theory, Ser. B"},{"key":"9545_CR46","doi-asserted-by":"crossref","first-page":"351","DOI":"10.1137\/0603036","volume":"3","author":"M. Yannakakis","year":"1982","unstructured":"Yannakakis, M.: The complexity of the partial order dimension problem. SIAM J. Algebr. Discrete Methods 3, 351\u2013358 (1982)","journal-title":"SIAM J. Algebr. Discrete Methods"}],"container-title":["Algorithmica"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00453-011-9545-y.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/article\/10.1007\/s00453-011-9545-y\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00453-011-9545-y","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,6,12]],"date-time":"2019-06-12T19:43:10Z","timestamp":1560368590000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/s00453-011-9545-y"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2011,7,14]]},"references-count":46,"journal-issue":{"issue":"1","published-print":{"date-parts":[[2012,9]]}},"alternative-id":["9545"],"URL":"https:\/\/doi.org\/10.1007\/s00453-011-9545-y","relation":{},"ISSN":["0178-4617","1432-0541"],"issn-type":[{"value":"0178-4617","type":"print"},{"value":"1432-0541","type":"electronic"}],"subject":[],"published":{"date-parts":[[2011,7,14]]}}}