{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,10,12]],"date-time":"2025-10-12T04:57:12Z","timestamp":1760245032866},"publisher-location":"Berlin, Heidelberg","reference-count":33,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783540194880"},{"type":"electronic","value":"9783540392910"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[1988]]},"DOI":"10.1007\/3-540-19488-6_105","type":"book-chapter","created":{"date-parts":[[2012,2,25]],"date-time":"2012-02-25T20:13:57Z","timestamp":1330200837000},"page":"38-51","source":"Crossref","is-referenced-by-count":37,"title":["Problems easy for tree-decomposable graphs extended abstract"],"prefix":"10.1007","author":[{"given":"Stefan","family":"Arnborg","sequence":"first","affiliation":[]},{"given":"Jens","family":"Lagergren","sequence":"additional","affiliation":[]},{"given":"Detlef","family":"Seese","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2005,5,31]]},"reference":[{"key":"3_CR1","unstructured":"Aho, Hopcroft and Ullman, Design and Analysis of Computer Algorithms Addison-Wesley 1972."},{"key":"3_CR2","doi-asserted-by":"crossref","first-page":"101","DOI":"10.1109\/TR.1978.5220267","volume":"R-27","author":"S. Arnborg","year":"1978","unstructured":"S. Arnborg, Reduced State Enumeration-Another Algorithm for Reliability Evaluation, IEEE Trans. Reliability R-27 (1978), 101\u2013105.","journal-title":"IEEE Trans. Reliability"},{"key":"3_CR3","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 (1985), 2\u201333.","journal-title":"BIT"},{"key":"3_CR4","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. and Discr. Methods 8(1987), 277\u2013284.","journal-title":"SIAM J. Alg. and Discr. Methods"},{"key":"3_CR5","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. and Discr. Methods 7(1986), 305\u2013314.","journal-title":"SIAM J. Alg. and Discr. Methods"},{"key":"3_CR6","unstructured":"S. Arnborg and A. Proskurowski, Linear Time Algorithms for NP-hard Problems on Graphs Embedded in k-trees, to app.."},{"volume-title":"Handbook of Mathematical Logic","year":"1977","key":"3_CR7","unstructured":"J. Barwise(ed.), Handbook of Mathematical Logic, Amsterdam, North-Holland 1977."},{"key":"3_CR8","doi-asserted-by":"crossref","first-page":"216","DOI":"10.1016\/0196-6774(87)90039-3","volume":"8","author":"M.W. Bern","year":"1987","unstructured":"M.W. Bern, E.L. Lawler, and A.L. Wong, Linear time computation of optimal subgraphs of decomposable graphs,J. of Algorithms 8(1987) 216\u2013235.","journal-title":"J. of Algorithms"},{"key":"3_CR9","volume-title":"Nonserial Dynamic Programming","author":"U. Bertele","year":"1972","unstructured":"U. Bertele and F. Brioschi, Nonserial Dynamic Programming. Academic Press, New York, 1972."},{"key":"3_CR10","doi-asserted-by":"crossref","unstructured":"H.L. Bodlaender, Dynamic Programming on Graphs with Bounded Tree-width, Ph D thesis, MIT 1987.","DOI":"10.1007\/3-540-19488-6_110"},{"key":"3_CR11","unstructured":"H.L. Bodlaender, Classes of Graphs with Bounded Tree-width, preprint, Dec 1986."},{"key":"3_CR12","unstructured":"K. Compton and C.W. Henson, A new method for proving lower bounds on the computational complexity of first-order theories, Manuscript."},{"key":"3_CR13","doi-asserted-by":"crossref","first-page":"163","DOI":"10.1016\/0166-218X(81)90013-5","volume":"3","author":"D.G. Corneil","year":"1981","unstructured":"D.G. Corneil, H. Lerchs and L. Stewart Burlingham, Complement Reducible Graphs, Discrete Appl. Math. 3 (1981), 163\u2013174.","journal-title":"Discrete Appl. Math."},{"key":"3_CR14","unstructured":"B. Courcelle, Recognizability and Second-Order Definability for Sets of Finite Graphs,Preprint, Universite de Bordeaux, I-8634, Jan 1987."},{"key":"3_CR15","first-page":"819","volume":"12","author":"J.E. Doner","year":"1965","unstructured":"J.E. Doner, Decidability of the Weak Second-Order theory of two Successors, Abstract 65T-468, Notices Amer. Math. Soc. 12(1965), 819, ibid. (1966), 513","journal-title":"Abstract 65T-468, Notices Amer. Math. Soc."},{"key":"3_CR16","unstructured":"R. Fagin, Generalized First-Order Spectra and Polynomial-Time Recognizable Sets, in Complexity and Computation, edited by R. Karp, SIAM-AMS Proceedings 7."},{"key":"3_CR17","volume-title":"Computers and Intractability","author":"M.R. Garey","year":"1979","unstructured":"M.R. Garey and D.S. Johnson, Computers and Intractability, W.H. Freeman and Company, San Francisco (1979)."},{"key":"3_CR18","doi-asserted-by":"crossref","unstructured":"Y. Gurevich, Monadic Second-Order Theories, Ch XIII of Model-Theoretic Logics, Ed. Barwise and Feferman, Springer-Verlag, New York 1985, 479\u2013506","DOI":"10.1017\/9781316717158.019"},{"key":"3_CR19","unstructured":"S.T. Hedetniemi, Open problems concerning the theory of algorithms on partial k-trees, working paper 1987."},{"key":"3_CR20","doi-asserted-by":"crossref","unstructured":"H. Immerman, Languages which capture Complexity Classes, proceedings of the 15th annual ACM Symposiom on the Theory of Computing, 1983 347\u2013354.","DOI":"10.1145\/800061.808765"},{"key":"3_CR21","doi-asserted-by":"crossref","first-page":"434","DOI":"10.1016\/0196-6774(85)90012-4","volume":"6","author":"D.S. Johnson","year":"1984","unstructured":"D.S. Johnson, The NP-Completeness Column: An Ongoing Guide, J. of Algorithms 6(1984) 434\u2013451.","journal-title":"J. of Algorithms"},{"key":"3_CR22","doi-asserted-by":"crossref","first-page":"285","DOI":"10.1016\/0196-6774(87)90043-5","volume":"8","author":"D.S. Johnson","year":"1987","unstructured":"D.S. Johnson, The NP-Completeness Column: An Ongoing Guide, J. of Algorithms 8(1987) 285\u2013303.","journal-title":"J. of Algorithms"},{"key":"3_CR23","unstructured":"M.O.Rabin, A simple Method of Undecidability proofs and some applications, In Log. Meth. Phil. Sci. Proc Jerusalem, 1964 58\u201368."},{"key":"3_CR24","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.D. Seymour, Graph Minors II. Algorithmic Aspects of Tree Width, Journal of Algorithms 7 (1986), 309\u2013322.","journal-title":"Journal of Algorithms"},{"key":"3_CR25","doi-asserted-by":"crossref","first-page":"384","DOI":"10.1137\/0132031","volume":"32","author":"A. Rosenthal","year":"1977","unstructured":"A. Rosenthal, Computing the Reliability of a Complex Network, SIAM J. Appl. Math. 32 (1977) 384\u2013393.","journal-title":"SIAM J. Appl. Math."},{"key":"3_CR26","unstructured":"J.R. Schoenfield, Mathematical Logic, Reading 1967, Addison-Wesley."},{"key":"3_CR27","unstructured":"P.Scheffler Linear-time Algorithms for NP-complete problems restricted to partial k-trees, Manuscript."},{"key":"3_CR28","unstructured":"P.SchefflerManuscript."},{"key":"3_CR29","unstructured":"D.Seese, Tree-partite Graphs and the Complexity of Algorithms, Preprint, P-Math 08\/86, Akademie der Wissenschaften der DDR, Karl Weierstrass Institut f\u00fcr Mathematik"},{"key":"3_CR30","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(1982) 623\u2013641.","journal-title":"J. ACM"},{"key":"3_CR31","doi-asserted-by":"crossref","first-page":"57","DOI":"10.1007\/BF01691346","volume":"2","author":"J.W. Thatcher","year":"1968","unstructured":"J.W. Thatcher, J.B. Wright, Generalized Finite Automata Theory with an Application to a Decision Problem in Second-Order Logic, Mathematical Systems Theory 2(1968), 57\u201381.","journal-title":"Mathematical Systems Theory"},{"key":"3_CR32","unstructured":"T.V.Wimer, Ph D Thesis."},{"key":"3_CR33","unstructured":"T.V.Wimer, S.T.Hedetniemi, and R.Laskar, A methodology for constructing linear graph algorithms, DCS, Clemson University, September 1985."}],"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_105.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2020,11,17]],"date-time":"2020-11-17T20:17:23Z","timestamp":1605644243000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/3-540-19488-6_105"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[1988]]},"ISBN":["9783540194880","9783540392910"],"references-count":33,"URL":"https:\/\/doi.org\/10.1007\/3-540-19488-6_105","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[1988]]}}}