{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,9,6]],"date-time":"2024-09-06T22:55:18Z","timestamp":1725663318818},"publisher-location":"Berlin, Heidelberg","reference-count":22,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783540515425"},{"type":"electronic","value":"9783540482376"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[1989]]},"DOI":"10.1007\/3-540-51542-9_48","type":"book-chapter","created":{"date-parts":[[2012,2,25]],"date-time":"2012-02-25T16:08:12Z","timestamp":1330186092000},"page":"577-590","source":"Crossref","is-referenced-by-count":11,"title":["On linear time minor tests and depth first search"],"prefix":"10.1007","author":[{"given":"Hans L.","family":"Bodlaender","sequence":"first","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2005,5,26]]},"reference":[{"key":"48_CR1","doi-asserted-by":"crossref","first-page":"2","DOI":"10.1007\/BF01934985","volume":"25","author":"S. Arnborg","year":"1985","unstructured":"S. Arnborg. Efficient algorithms for combinatorial problems on graphs with bounded decomposability \u2014 A survey. BIT, 25:2\u201323, 1985.","journal-title":"BIT"},{"key":"48_CR2","doi-asserted-by":"crossref","unstructured":"S. Arnborg, J. Lagergren, and D. Seese. Problems easy for tree-decomposable graphs (extended abstract). In Proc. 15'th ICALP, pages 38\u201351. Springer Verlag, Lect. Notes in Comp. Sc. 317, 1988.","DOI":"10.1007\/3-540-19488-6_105"},{"key":"48_CR3","volume-title":"Linear time algorithms for NP-hard problems on graphs embedded in k-trees. Trita-na-8404","author":"S. Arnborg","year":"1984","unstructured":"S. Arnborg and A. Proskurowski. Linear time algorithms for NP-hard problems on graphs embedded in k-trees. Trita-na-8404, Dept. of Num. Anal. and Comp. Sci., Royal Institute of Technology, Stockholm, Sweden, 1984."},{"key":"48_CR4","doi-asserted-by":"crossref","unstructured":"H. L. Bodlaender. NC-algorithms for graphs with small treewidth. In Proc. Workshop on Graph-Theoretic Concepts in Computer Science WG'88, pages 1\u201310. Springer Verlag, LNCS 344, 1988.","DOI":"10.1007\/3-540-50728-0_32"},{"key":"48_CR5","doi-asserted-by":"crossref","unstructured":"B. Courcelle. The monadic second-order logic of graphs I: Recognizable sets of finite graphs. Technical Report I-8837, Dept. Comp. Sc, Univ. Bordeaux 1, 1988.","DOI":"10.1007\/BF02088013"},{"key":"48_CR6","doi-asserted-by":"crossref","unstructured":"B. Courcelle. The monadic second-order logic of graphs III: Treewidth, forbidden minors and complexity issues. Manuscript, 1988.","DOI":"10.1007\/BF02088013"},{"key":"48_CR7","first-page":"464","volume":"2","author":"P. Erd\u00f6s","year":"1935","unstructured":"P. Erd\u00f6s and G. Szekeres. A combinatorial problem in geometry. Compos. Math., 2:464\u2013470, 1935.","journal-title":"Compos. Math."},{"key":"48_CR8","doi-asserted-by":"crossref","first-page":"549","DOI":"10.1007\/BF01762131","volume":"3","author":"M. R. Fellows","year":"1988","unstructured":"M. R. Fellows, D. K. Friesen, and M. A. Langston. On finding optimal and near-optimal lineal spanning trees. Algorithmica, 3:549\u2013560, 1988.","journal-title":"Algorithmica"},{"key":"48_CR9","unstructured":"M. R. Fellows and M. A. Langston. Fast search algorithms for graph layout permutation problems. Technical Report CS-88-189, Dept. of Comp. Sc., Washington State Univ., 1988."},{"key":"48_CR10","doi-asserted-by":"crossref","unstructured":"M. R. Fellows and M. A. Langston. On seach, decision and the efficiency of polynomial-time algorithms. Technical Report CS-88-190, Dept. of Comp. Sc., Washington State Univ., 1988. To appear in Proc. STOC '89.","DOI":"10.1145\/73007.73055"},{"key":"48_CR11","unstructured":"M. R. Fellows and M. A. Langston. On well-partial-order theory and its application to combinatorial problems of VLSI design. Technical Report CS-88-188, Dept. of Comp. Sc., Washington State Univ., 1988."},{"key":"48_CR12","volume-title":"Computers and Intractability, A Guide to the Theory of NP-Completeness","author":"M. R. Garey","year":"1979","unstructured":"M. R. Garey and D. S. Johnson. Computers and Intractability, A Guide to the Theory of NP-Completeness. W.H. Freeman and Company, New York, 1979."},{"key":"48_CR13","doi-asserted-by":"publisher","first-page":"549","DOI":"10.1145\/321850.321852","volume":"21","author":"J. E. Hopcroft","year":"1974","unstructured":"J. E. Hopcroft and R. E. Tarjan. Efficient planarity testing. J. ACM, 21:549\u2013568, 1974.","journal-title":"J. ACM"},{"key":"48_CR14","doi-asserted-by":"crossref","unstructured":"C. Lautemann. Efficient algorithms on context-free graph languages. In Proc. 15'th ICALP, pages 362\u2013378. Springer Verlag, Lect. Notes in Comp. Sc. 317, 1988.","DOI":"10.1007\/3-540-19488-6_128"},{"key":"48_CR15","doi-asserted-by":"publisher","first-page":"18","DOI":"10.1145\/42267.42268","volume":"35","author":"N. Megiddo","year":"1988","unstructured":"N. Megiddo, S. L. Hakimi, M. R. Garey, D. S. Johnson, and C. H. Papadimitriou. The complexity of searching a graph. J. ACM, 35:18\u201344, 1988.","journal-title":"J. ACM"},{"key":"48_CR16","volume-title":"Data Structures and Algorithms 2. Graph Algorithms and NP-Completeness","author":"K. Mehlhorn","year":"1984","unstructured":"K. Mehlhorn. Data Structures and Algorithms 2. Graph Algorithms and NP-Completeness. Springer Verlag, Berlin, 1984."},{"key":"48_CR17","first-page":"239","volume":"25","author":"B. Monien","year":"1985","unstructured":"B. Monien. How to find long paths efficiently. Annals of Disc. Math., 25:239\u2013254, 1985.","journal-title":"Annals of Disc. Math."},{"key":"48_CR18","unstructured":"N. Robertson and P. Seymour. Graph minors. XVI. Wagner's conjecture. To appear."},{"key":"48_CR19","doi-asserted-by":"crossref","first-page":"309","DOI":"10.1016\/0196-6774(86)90023-4","volume":"7","author":"N. Robertson","year":"1986","unstructured":"N. Robertson and P. Seymour. Graph minors. II. Algorithmic aspects of tree-width. J. of Algorithms, 7:309\u2013322, 1986.","journal-title":"J. of Algorithms"},{"key":"48_CR20","doi-asserted-by":"crossref","unstructured":"N. Robertson and P. Seymour. Graph minors. XIII. The disjoint paths problem. Manuscript., 1986.","DOI":"10.1016\/0095-8956(86)90031-6"},{"key":"48_CR21","volume-title":"Linear-time algorithms for NP-complete problems restricted to partial k-trees. Report R-MATH-03\/87","author":"P. Scheffler","year":"1987","unstructured":"P. Scheffler. Linear-time algorithms for NP-complete problems restricted to partial k-trees. Report R-MATH-03\/87, Karl-Weierstrass-Institut F\u00fcr Mathematik, Berlin, GDR, 1987."},{"key":"48_CR22","unstructured":"T. Wimer. Linear algorithms on k-terminal graphs. PhD thesis, Dept. of Computer Science, Clemson University, 1987."}],"container-title":["Lecture Notes in Computer Science","Algorithms and Data Structures"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/3-540-51542-9_48.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2021,12,30]],"date-time":"2021-12-30T21:57:16Z","timestamp":1640901436000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/3-540-51542-9_48"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[1989]]},"ISBN":["9783540515425","9783540482376"],"references-count":22,"URL":"https:\/\/doi.org\/10.1007\/3-540-51542-9_48","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[1989]]}}}