{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,3,21]],"date-time":"2025-03-21T21:40:09Z","timestamp":1742593209707,"version":"3.40.2"},"publisher-location":"Berlin, Heidelberg","reference-count":30,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783540522928"},{"type":"electronic","value":"9783540469506"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[1990]]},"DOI":"10.1007\/3-540-52292-1_17","type":"book-chapter","created":{"date-parts":[[2012,2,25]],"date-time":"2012-02-25T21:29:52Z","timestamp":1330205392000},"page":"232-244","source":"Crossref","is-referenced-by-count":3,"title":["Improved self-reduction algorithms for graphs with bounded treewidth"],"prefix":"10.1007","author":[{"given":"Hans L.","family":"Bodlaender","sequence":"first","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2005,6,1]]},"reference":[{"key":"17_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":"17_CR2","doi-asserted-by":"crossref","first-page":"277","DOI":"10.1137\/0608024","volume":"8","author":"S. Arnborg","year":"1987","unstructured":"S. Arnborg, D. G. Corneil, and A. Proskurowski. Complexity of finding embeddings in a k-tree. SIAM J. Alg. Disc. Meth., 8:277\u2013284, 1987.","journal-title":"SIAM J. Alg. Disc. Meth."},{"key":"17_CR3","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":"17_CR4","doi-asserted-by":"crossref","first-page":"305","DOI":"10.1137\/0607033","volume":"7","author":"S. Arnborg","year":"1986","unstructured":"S. Arnborg and A. Proskurowski. Characterization and recognition of partial 3-trees. SIAM J. Alg. Disc. Meth., 7:305\u2013314, 1986.","journal-title":"SIAM J. Alg. Disc. Meth."},{"key":"17_CR5","doi-asserted-by":"publisher","first-page":"11","DOI":"10.1016\/0166-218X(89)90031-0","volume":"23","author":"S. Arnborg","year":"1989","unstructured":"S. Arnborg and A. Proskurowski. Linear time algorithms for NP-hard problems restricted to partial k-trees. Disc. Appl. Math., 23:11\u201324, 1989.","journal-title":"Disc. Appl. Math."},{"key":"17_CR6","unstructured":"H. L. Bodlaender. Dynamic programming algorithms on graphs with bounded tree-width. Tech. rep., Lab. for Comp. Science, M.I.T., 1987. Ext. abstract in proceedings ICALP 88."},{"key":"17_CR7","doi-asserted-by":"crossref","unstructured":"H. L. Bodlaender. NC-algorithms for graphs with small treewidth. In J. van Leeuwen, editor, 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":"17_CR8","doi-asserted-by":"crossref","unstructured":"H. L. Bodlaender. Polynomial algorithms for graph isomorphism and chromatic index on partial k-trees. In Proc. 1st Scandinavian Workshop on Algorithm Theory, pages 223\u2013232, 1988.","DOI":"10.1007\/3-540-19487-8_26"},{"key":"17_CR9","unstructured":"H. L. Bodlaender. Some classes of graphs with bounded treewidth. Bulletin of the EATCS, 1988."},{"key":"17_CR10","unstructured":"D. Brown, M. Fellows, and M. Langston. Nonconstructive polynomial-time decidability and self-reducibility. In Princeton Forum on Algorithms and Complexity, 1987."},{"key":"17_CR11","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":"17_CR12","doi-asserted-by":"publisher","first-page":"157","DOI":"10.1016\/0020-0190(87)90054-8","volume":"26","author":"M. R. Fellows","year":"1987","unstructured":"M. R. Fellows and M. A. Langston. Nonconstructive advances in polynomial-time complexity. Inform. Proc. Letters, 26:157\u2013162, 1987.","journal-title":"Inform. Proc. Letters"},{"key":"17_CR13","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":"17_CR14","doi-asserted-by":"crossref","unstructured":"M. R. Fellows and M. A. Langston. Layout permutation problems and well-partially-ordered sets. In 5th MIT Conf. on Advanced Research in VLSI, pages 315\u2013327, 1988.","DOI":"10.7551\/mitpress\/1102.003.0025"},{"key":"17_CR15","doi-asserted-by":"publisher","first-page":"727","DOI":"10.1145\/44483.44491","volume":"35","author":"M. R. Fellows","year":"1988","unstructured":"M. R. Fellows and M. A. Langston. Nonconstructive tools for proving polynomial-time decidability. J. ACM, 35:727\u2013739, 1988.","journal-title":"J. ACM"},{"key":"17_CR16","doi-asserted-by":"crossref","unstructured":"M. R. Fellows and M. A. Langston. On search, decision and the efficiency of polynomial-time algorithms. In Proc. STOC, pages 501\u2013512, 1989.","DOI":"10.1145\/73007.73055"},{"key":"17_CR17","doi-asserted-by":"publisher","first-page":"205","DOI":"10.1016\/0304-3975(86)90146-5","volume":"47","author":"L. M. Kirousis","year":"1986","unstructured":"L. M. Kirousis and C. H. Papadimitriou. Searching and pebbling. Theor. Comp. Sc., 47:205\u2013218, 1986.","journal-title":"Theor. Comp. Sc."},{"key":"17_CR18","volume-title":"Recontamination does not help to search a graph","author":"A. S. LaPaugh","year":"1982","unstructured":"A. S. LaPaugh. Recontamination does not help to search a graph. Technical report, Comp. Sci. Dept, Princeton Univ., New Yersey, 1982."},{"key":"17_CR19","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":"17_CR20","doi-asserted-by":"crossref","first-page":"465","DOI":"10.1007\/BF00264496","volume":"16","author":"T. Lengauer","year":"1981","unstructured":"T. Lengauer. Black-white pebbles and graph separation. Acta Inf., 16:465\u2013475, 1981.","journal-title":"Acta Inf."},{"key":"17_CR21","unstructured":"J. Matous\u011bk and R. Thomas. Algorithms finding tree-decompositions of graphs. Unpublished paper, 1988."},{"key":"17_CR22","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":"17_CR23","doi-asserted-by":"publisher","first-page":"209","DOI":"10.1016\/0304-3975(88)90028-X","volume":"58","author":"B. Monien","year":"1988","unstructured":"B. Monien and I. H. Sudborough. Min cut is NP-complete for edge weighted trees. Theor. Comp. Sc., 58:209\u2013229, 1988.","journal-title":"Theor. Comp. Sc."},{"key":"17_CR24","unstructured":"N. Robertson and P. Seymour. Graph minors. IV. Tree-width and well-quadi-ordering. Manuscript."},{"key":"17_CR25","unstructured":"N. Robertson and P. Seymour. Graph minors. XVI. Wagner's conjecture. To appear."},{"key":"17_CR26","doi-asserted-by":"publisher","first-page":"49","DOI":"10.1016\/0095-8956(84)90013-3","volume":"36","author":"N. Robertson","year":"1984","unstructured":"N. Robertson and P. Seymour. Graph minors. III. Planar tree-width. J. Comb. Theory Series B, 36:49\u201364, 1984.","journal-title":"J. Comb. Theory Series B"},{"key":"17_CR27","doi-asserted-by":"publisher","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. Algorithms, 7:309\u2013322, 1986.","journal-title":"J. Algorithms"},{"key":"17_CR28","unstructured":"N. Robertson and P. Seymour. Graph minors. X. Obstructions to tree-decompositions. Manuscript., 1986."},{"key":"17_CR29","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":"17_CR30","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."}],"container-title":["Lecture Notes in Computer Science","Graph-Theoretic Concepts in Computer Science"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/3-540-52292-1_17.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,3,21]],"date-time":"2025-03-21T21:00:16Z","timestamp":1742590816000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/3-540-52292-1_17"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[1990]]},"ISBN":["9783540522928","9783540469506"],"references-count":30,"URL":"https:\/\/doi.org\/10.1007\/3-540-52292-1_17","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[1990]]}}}