{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,4,16]],"date-time":"2026-04-16T09:58:17Z","timestamp":1776333497491,"version":"3.51.2"},"publisher-location":"Berlin, Heidelberg","reference-count":35,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"value":"9783540194880","type":"print"},{"value":"9783540392910","type":"electronic"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[1988]]},"DOI":"10.1007\/3-540-19488-6_110","type":"book-chapter","created":{"date-parts":[[2012,2,25]],"date-time":"2012-02-25T15:15:27Z","timestamp":1330182927000},"page":"105-118","source":"Crossref","is-referenced-by-count":134,"title":["Dynamic programming on graphs with bounded treewidth"],"prefix":"10.1007","author":[{"given":"Hans L.","family":"Bodlaender","sequence":"first","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2005,5,31]]},"reference":[{"key":"8_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":"8_CR2","doi-asserted-by":"crossref","first-page":"277","DOI":"10.1137\/0608024","volume":"8","author":"S. Arnborg","year":"1987","unstructured":"S. Arnborg, D. 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":"8_CR3","doi-asserted-by":"crossref","unstructured":"S. Arnborg, J. Lagergren, and D. Seese. Which problems are easy for tree-decomposable graphs. 1987. Ext. abstract to appear in proc. ICALP 88.","DOI":"10.1007\/3-540-19488-6_105"},{"key":"8_CR4","doi-asserted-by":"crossref","unstructured":"S. Arnborg, J. Lagergren, and D. Seese. Which problems are easy for tree-decomposable graphs. 1988. In these proceedings.","DOI":"10.1007\/3-540-19488-6_105"},{"key":"8_CR5","volume-title":"Linear time algorithms for NP-hard problems on graphs embedded in k-trees","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":"8_CR6","first-page":"265","volume-title":"Approximation algorithms for NP-complete problems on planar graphs","author":"B. S. Baker","year":"1983","unstructured":"B. S. Baker. Approximation algorithms for NP-complete problems on planar graphs. In Proceedings 24th Ann. Symp. on Foundations of Computer Science, pages 265\u2013273, IEEE Computer Society, Los Angeles, 1983, Preliminary version."},{"key":"8_CR7","doi-asserted-by":"crossref","unstructured":"M. W. Bern, E. L. Lawler, and A. L. Wong. Why certain subgraph computations require only linear time. In Proc. 26th Symp. on Foundations of Computer Science, pages 117\u2013125, 1985.","DOI":"10.1109\/SFCS.1985.66"},{"key":"8_CR8","series-title":"Technical Report RUU-CS-86-22","volume-title":"Classes of Graphs with Bounded Treewidth","author":"H. L. Bodlaender","year":"1986","unstructured":"H. L. Bodlaender. Classes of Graphs with Bounded Treewidth. Technical Report RUU-CS-86-22, Dept. of Comp. Science, University of Utrecht, Utrecht, 1986."},{"key":"8_CR9","doi-asserted-by":"crossref","unstructured":"H. L. Bodlaender. Dynamic programming algorithms on graphs with bounded tree-width. Tech. Rep., Lab. for Comp. Science, M.I.T., 1987.","DOI":"10.1007\/3-540-19488-6_110"},{"key":"8_CR10","series-title":"Technical Report RUU-CS-88-4","volume-title":"NC-algorithms for graphs with small treewidth","author":"H. L. Bodlaender","year":"1988","unstructured":"H. L. Bodlaender. NC-algorithms for graphs with small treewidth. Technical Report RUU-CS-88-4, Dept. of Comp. Science, Univ. of Utrecht, Utrecht, 1988."},{"key":"8_CR11","unstructured":"H. L. Bodlaender. Polynomial algorithms for Chromatic Index and Graph Isomorphism on partial k-trees. Tech. Rep. RUU-CS-87-17, Dept. of Comp. Sci., Univ. of Utrecht, 1987."},{"key":"8_CR12","doi-asserted-by":"crossref","first-page":"41","DOI":"10.1016\/0020-0190(75)90011-3","volume":"4","author":"E. J. Cockayne","year":"1975","unstructured":"E. J. Cockayne, S. E. Goodman, and S. T. Hedetniemi. A linear algorithm for the domination number of a tree. Inform. Proc. Letters, 4:41\u201344, 1975.","journal-title":"Inform. Proc. Letters"},{"key":"8_CR13","first-page":"107","volume":"19A","author":"C. J. Colbourn","year":"1985","unstructured":"C. J. Colbourn and L. K. Stewart. Dominating cycles in series-parallel graphs. Ans Combinatorica, 19A:107\u2013112, 1985.","journal-title":"Ans Combinatorica"},{"key":"8_CR14","doi-asserted-by":"crossref","first-page":"27","DOI":"10.1016\/0166-218X(85)90057-5","volume":"10","author":"D. Coppersmith","year":"1985","unstructured":"D. Coppersmith and U. Vishkin. Solving NP-hard problems in\u2019 almost trees': vertex cover. Disc. Applied Match, 10:27\u201345, 1985.","journal-title":"Disc. Applied Match"},{"key":"8_CR15","doi-asserted-by":"crossref","first-page":"287","DOI":"10.1007\/BF02591867","volume":"26","author":"G. Cornu\u00e9jols","year":"1983","unstructured":"G. Cornu\u00e9jols, D. Naddef, and W. R. Pulleyblank. Halin graphs and the traveling salesman problem. Math. Programming, 26:287\u2013294, 1983.","journal-title":"Math. Programming"},{"key":"8_CR16","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":"8_CR17","doi-asserted-by":"crossref","first-page":"459","DOI":"10.1145\/828.322439","volume":"31","author":"Y. Gurevich","year":"1984","unstructured":"Y. Gurevich, L. Stockmeyer, and U. Vishkin. Solving NP-hard problems on graphs that are almost trees and an application to facility location problems. J. Assoc. Comp. Mach., 31:459\u2013473, 1984.","journal-title":"J. Assoc. Comp. Mach."},{"key":"8_CR18","doi-asserted-by":"crossref","first-page":"379","DOI":"10.1137\/0607043","volume":"7","author":"R. Hassin","year":"1986","unstructured":"R. Hassin and A. Tamir. Efficient algorithms for optimization and selection on series-parallel graphs. SIAM J. Alg. Disc. Meth., 7:379\u2013389, 1986.","journal-title":"SIAM J. Alg. Disc. Meth."},{"key":"8_CR19","volume-title":"A linear algorithm for the domination number of a cactus. Report 433","author":"S. T. Hedetniemi","year":"1983","unstructured":"S. T. Hedetniemi, R. Laskar, and J. Pfaff. A linear algorithm for the domination number of a cactus. Report 433, Dept. of Math. Sc., Clemson Univ., Clemson, S.C., 1983."},{"key":"8_CR20","volume-title":"Algebra. Graduate Texts in Mathematics 73","author":"T. W. Hungerford","year":"1974","unstructured":"T. W. Hungerford. Algebra. Graduate Texts in Mathematics 73, Springer-Verlag, New York, 1974."},{"key":"8_CR21","doi-asserted-by":"crossref","first-page":"299","DOI":"10.1016\/0166-218X(83)90003-3","volume":"5","author":"T. Kikuno","year":"1983","unstructured":"T. Kikuno, N. Yoshida, and Y. Kakuda. A linear algorithm for the domination number of a series-parallel graph. Discrete Appl. Math., 5:299\u2013311, 1983.","journal-title":"Discrete Appl. Math."},{"key":"8_CR22","doi-asserted-by":"crossref","first-page":"420","DOI":"10.1137\/0605040","volume":"5","author":"R. Laskar","year":"1984","unstructured":"R. Laskar, J. Pfaff, S. M. Hedetniemi, and S. T. Hedetniemi. On the algorithmic complexity of total domination. SIAM J. Alg. Disc. Meth., 5:420\u2013425, 1984.","journal-title":"SIAM J. Alg. Disc. Meth."},{"key":"8_CR23","doi-asserted-by":"crossref","unstructured":"B. Monien and I. Sudborough. Min cut is NP-complete for edge weighted trees. In Proc. of Int. Conf. Automata, Languages, and Programming ICALP '86, pages 265\u2013274, Springer Verlag Lecture Notes in Comp. Science, Vol 226, 1986.","DOI":"10.1007\/3-540-16761-7_76"},{"key":"8_CR24","first-page":"207","volume-title":"Bandwidth-constrained NP-complete problems","author":"B. Monien","year":"1981","unstructured":"B. Monien and I. H. Sudborough. Bandwidth-constrained NP-complete problems. In Proc. 13th Ann. ACM Symp. on Theory of Computing, pages 207\u2013217, Assoc. For Computing Machinery, New York, 1981."},{"key":"8_CR25","volume-title":"Efficient vertex-and edge-coloring of outerplanar graphs. Report UO-CIS-TR-82-5","author":"A. Proskurowski","year":"1982","unstructured":"A. Proskurowski and M. M. Sys\u0142o. Efficient vertex-and edge-coloring of outerplanar graphs. Report UO-CIS-TR-82-5, Dept. of Computer and Information Sc., Univ. of Oregon Eugene, Ore., 1982."},{"key":"8_CR26","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":"8_CR27","unstructured":"N. Robertson and P. Seymour. Graph minors. X. Obstructions to tree-decompositions. 1986. Manuscript."},{"key":"8_CR28","doi-asserted-by":"crossref","unstructured":"N. Robertson and P. Seymour. Graph minors. XIII. The disjoint paths problem. 1986. Manuscript.","DOI":"10.1016\/0095-8956(86)90031-6"},{"key":"8_CR29","unstructured":"P. Scheffler and D. Seese. A combinatorial and logical approach to linear-time computability. 1986. Extended abstract."},{"key":"8_CR30","unstructured":"I. H. Sudborough. \u201cCutwidth\u201d and related graph problems. Bulletin of the EATCS, 79\u2013110, Feb. 1987."},{"key":"8_CR31","first-page":"342","volume-title":"Proc. WG'83 International Workshop on Graph Theoretic Concepts in Computer Science","author":"M. M. Sys\u0142o","year":"1983","unstructured":"M. M. Sys\u0142o. NP-complete problems on some tree-structured graphs: a review. In M. Nagl and J. Perl, editors, Proc. WG'83 International Workshop on Graph Theoretic Concepts in Computer Science, pages 342\u2013353, Univ. Verlag Rudolf Trauner, Linz, West Germany, 1983."},{"key":"8_CR32","doi-asserted-by":"crossref","first-page":"91","DOI":"10.1016\/0304-3975(82)90133-5","volume":"17","author":"M. M. Sys\u0142o","year":"1982","unstructured":"M. M. Sys\u0142o. The subgraph isomorphism problem for outerplanar graphs. Theor. Comput. Science, 17:91\u201397, 1982.","journal-title":"Theor. Comput. Science"},{"key":"8_CR33","doi-asserted-by":"crossref","first-page":"623","DOI":"10.1145\/322326.322328","volume":"29","author":"K. Takamizawa","year":"1982","unstructured":"K. Takamizawa, T. Nishizeki, and N. Saito. Linear-time computability of combinatorial problems on series-parallel graphs. J. ACM, 29:623\u2013641, 1982.","journal-title":"J. ACM"},{"key":"8_CR34","doi-asserted-by":"crossref","first-page":"159","DOI":"10.1002\/net.3230130202","volume":"13","author":"J. Wald","year":"1983","unstructured":"J. Wald and C. Colbourn. Steiner trees, partial 2-trees, and minimum IFI networks. Networks, 13:159\u2013167, 1983.","journal-title":"Networks"},{"key":"8_CR35","volume-title":"Steiner trees in outerplanar graphs","author":"J. Wald","year":"1982","unstructured":"J. Wald and C. J. Colbourn. Steiner trees in outerplanar graphs. In Proc. 13th Southeastern Conf. on Combinatorics, Graph Theory, and Computing, Utilitas Mathematica Publishing, Winnipeg, Ont., 1982."}],"container-title":["Lecture Notes in Computer Science","Automata, Languages and Programming"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/3-540-19488-6_110.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2021,12,30]],"date-time":"2021-12-30T21:32:09Z","timestamp":1640899929000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/3-540-19488-6_110"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[1988]]},"ISBN":["9783540194880","9783540392910"],"references-count":35,"URL":"https:\/\/doi.org\/10.1007\/3-540-19488-6_110","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"value":"0302-9743","type":"print"},{"value":"1611-3349","type":"electronic"}],"subject":[],"published":{"date-parts":[[1988]]}}}