{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,9,6]],"date-time":"2024-09-06T23:19:00Z","timestamp":1725664740319},"publisher-location":"Berlin, Heidelberg","reference-count":22,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783540614227"},{"type":"electronic","value":"9783540685296"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[1996]]},"DOI":"10.1007\/3-540-61422-2_129","type":"book-chapter","created":{"date-parts":[[2012,2,26]],"date-time":"2012-02-26T21:36:55Z","timestamp":1330292215000},"page":"161-172","source":"Crossref","is-referenced-by-count":0,"title":["Vertex partitioning problems on partial k-trees"],"prefix":"10.1007","author":[{"given":"Arvind","family":"Gupta","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Damon","family":"Kaller","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Sanjeev","family":"Mahajan","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Tom","family":"Shermer","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2005,6,7]]},"reference":[{"key":"15_CR1","doi-asserted-by":"publisher","first-page":"308","DOI":"10.1016\/0196-6774(91)90006-K","volume":"12","author":"S. Arnborg","year":"1991","unstructured":"S. Arnborg, J. Lagergren, and D. Seese. Easy problems for tree decomposable graphs. J. Algorithms, 12:308\u2013340, 1991.","journal-title":"J. Algorithms"},{"key":"15_CR2","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. BIT, 25:2\u201333, 1985.","journal-title":"BIT"},{"key":"15_CR3","doi-asserted-by":"crossref","unstructured":"H.L. Bodlaender and K. Jansen. On the complexity of scheduling incompatible jobs with unit-times. In Lecture Notes in Computer Science (Proc. 18th MFCS), volume 711, pages 291\u2013300. Springer-Verlag, 1993.","DOI":"10.1007\/3-540-57182-5_21"},{"key":"15_CR4","doi-asserted-by":"publisher","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. Algorithms, 8:216\u2013235, 1987.","journal-title":"J. Algorithms"},{"key":"15_CR5","doi-asserted-by":"crossref","unstructured":"H.L. Bodlaender. Dynamic programming on graphs with bounded treewidth. In Lecture Notes in Computer Science (Proc. 15th ICALP), volume 317, pages 105\u2013119. Springer-Verlag, 1988.","DOI":"10.1007\/3-540-19488-6_110"},{"key":"15_CR6","doi-asserted-by":"crossref","unstructured":"H.L. Bodlaender. A linear time algorithm for finding tree-decompositions of small treewidth. In Proc. 25th STOC, pages 226\u2013234, 1993.","DOI":"10.1145\/167088.167161"},{"key":"15_CR7","doi-asserted-by":"publisher","first-page":"555","DOI":"10.1007\/BF01758777","volume":"7","author":"R.B. Borie","year":"1992","unstructured":"R.B. Borie, R.G. Parker, and C.A. Tovey. Automatic generation of linear-time algorithms from predicate calculus descriptions of problems on recursively constructed graph families. Algorithmica, 7:555\u2013581, 1992.","journal-title":"Algorithmica"},{"key":"15_CR8","first-page":"193","volume-title":"Handbook of Theoretical Computer Science, volume B","author":"B. Courcelle","year":"1990","unstructured":"B. Courcelle. Graph rewriting: an algebraic and logic approach. In J. van Leeuwen, editor, Handbook of Theoretical Computer Science, volume B, pages 193\u2013242. Elsevier, Amsterdam, 1990."},{"key":"15_CR9","doi-asserted-by":"publisher","first-page":"12","DOI":"10.1016\/0890-5401(90)90043-H","volume":"85","author":"B. Courcelle","year":"1990","unstructured":"B. Courcelle. The monadic second-order logic of graphs. I. Recognizable sets of finite graphs. Information and Computation, 85:12\u201375, 1990.","journal-title":"Information and Computation"},{"key":"15_CR10","doi-asserted-by":"publisher","first-page":"153","DOI":"10.1016\/0304-3975(91)90387-H","volume":"80","author":"B. Courcelle","year":"1991","unstructured":"B. Courcelle. The monadic second-order logic of graphs. V. On closing the gap between definability and recognizability. Theoret. Comput. Sci., 80:153\u2013202, 1991.","journal-title":"Theoret. Comput. Sci."},{"key":"15_CR11","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":"15_CR12","volume-title":"Tree Automata","author":"F. G\u00e9cseg","year":"1984","unstructured":"F. G\u00e9cseg and M. Steinby. Tree Automata. Akad\u00e9miai Kiad\u00f3, Budapest, 1984."},{"key":"15_CR13","unstructured":"J.E. Hopcroft and J.D. Ullman. Introduction to Automata Theory, Languages, and Computation. Addison-Wesley, 1979."},{"key":"15_CR14","doi-asserted-by":"crossref","unstructured":"D. Kaller. Definability equals recognizability of partial 3-trees, 1996. To appear.","DOI":"10.1007\/3-540-62559-3_20"},{"key":"15_CR15","doi-asserted-by":"crossref","unstructured":"D. Kaller, A. Gupta, and T. Shermer. The Xt-coloring problem. In Lecture Notes in Computer Science (Proc. 12th STACS), volume 900, pages 409\u2013420. Springer-Verlag, 1995.","DOI":"10.1007\/3-540-59042-0_92"},{"key":"15_CR16","doi-asserted-by":"crossref","unstructured":"D. Kaller, A. Gupta, and T. Shermer. Regular-factors in the complements of partial k-trees. In Lecture Notes in Computer Science (Proc. 4th WADS), volume 955, pages 403\u2013414. Springer-Verlag, 1995.","DOI":"10.1007\/3-540-60220-8_80"},{"key":"15_CR17","doi-asserted-by":"crossref","unstructured":"D.G. Kirkpatrick and P. Hell. On the complexity of a generalized matching problem. In Proc. 10th STOC, pages 240\u2013245, 1978.","DOI":"10.1145\/800133.804353"},{"key":"15_CR18","unstructured":"J. Lagergren, October 1994. Personal communication."},{"key":"15_CR19","doi-asserted-by":"crossref","first-page":"229","DOI":"10.1016\/0166-218X(94)90025-6","volume":"54","author":"S. Mahajan","year":"1994","unstructured":"S. Mahajan and J.G. Peters. Regularity and locality in k-terminal graphs. Disc. Appl. Math., 54:229\u2013250, 1994.","journal-title":"Disc. Appl. Math."},{"key":"15_CR20","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.D. Seymour. Graph minors. II. Algorithmic aspects of tree-width. J. Algorithms, 7:309\u2013322, 1986.","journal-title":"J. Algorithms"},{"key":"15_CR21","first-page":"133","volume-title":"Handbook of Theoretical Computer Science, volume B","author":"W. Thomas","year":"1990","unstructured":"W. Thomas. Automata on infinite objects. In J. van Leeuwen, editor, Handbook of Theoretical Computer Science, volume B, pages 133\u2013191. Elsevier, Amsterdam, 1990."},{"key":"15_CR22","doi-asserted-by":"crossref","first-page":"193","DOI":"10.1016\/0020-0190(89)90140-3","volume":"33","author":"E. Wanke","year":"1989","unstructured":"E. Wanke and M. Wiegers. Undecidability of the bandwidth problem on linear graph languages. Inform. Process. Lett., 33:193\u2013197, 1989.","journal-title":"Inform. Process. Lett."}],"container-title":["Lecture Notes in Computer Science","Algorithm Theory \u2014 SWAT'96"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/3-540-61422-2_129.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2020,11,17]],"date-time":"2020-11-17T21:06:00Z","timestamp":1605647160000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/3-540-61422-2_129"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[1996]]},"ISBN":["9783540614227","9783540685296"],"references-count":22,"URL":"https:\/\/doi.org\/10.1007\/3-540-61422-2_129","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[1996]]}}}