{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,12,16]],"date-time":"2025-12-16T12:12:24Z","timestamp":1765887144812},"publisher-location":"Berlin, Heidelberg","reference-count":14,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783642027765"},{"type":"electronic","value":"9783642027772"}],"license":[{"start":{"date-parts":[[2009,1,1]],"date-time":"2009-01-01T00:00:00Z","timestamp":1230768000000},"content-version":"unspecified","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2009]]},"DOI":"10.1007\/978-3-642-02777-2_6","type":"book-chapter","created":{"date-parts":[[2009,6,26]],"date-time":"2009-06-26T02:58:18Z","timestamp":1245985098000},"page":"45-50","source":"Crossref","is-referenced-by-count":17,"title":["Encoding Treewidth into SAT"],"prefix":"10.1007","author":[{"given":"Marko","family":"Samer","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Helmut","family":"Veith","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","reference":[{"issue":"2","key":"6_CR1","doi-asserted-by":"publisher","first-page":"277","DOI":"10.1137\/0608024","volume":"8","author":"S. Arnborg","year":"1987","unstructured":"Arnborg, S., Corneil, D.G., Proskurowski, A.: Complexity of finding embeddings in a k-tree. SIAM Journal on Algebraic and Discrete Methods\u00a08(2), 277\u2013284 (1987)","journal-title":"SIAM Journal on Algebraic and Discrete Methods"},{"key":"6_CR2","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"216","DOI":"10.1007\/11427186_20","volume-title":"Experimental and Efficient Algorithms","author":"E.H. Bachoore","year":"2005","unstructured":"Bachoore, E.H., Bodlaender, H.L.: New upper bound heuristics for treewidth. In: Nikoletseas, S.E. (ed.) WEA 2005. LNCS, vol.\u00a03503, pp. 216\u2013227. Springer, Heidelberg (2005)"},{"key":"6_CR3","doi-asserted-by":"crossref","unstructured":"Bachoore, E.H., Bodlaender, H.L.: A branch and bound algorithm for exact, upper, and lower bounds on treewidth. Technical Report UU-CS-2006-012, Department of Information and Computing Sciences, Utrecht University (2006)","DOI":"10.1007\/11775096_24"},{"key":"6_CR4","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1007\/978-3-540-30577-4_1","volume-title":"SOFSEM 2005: Theory and Practice of Computer Science","author":"H.L. Bodlaender","year":"2005","unstructured":"Bodlaender, H.L.: Discovering treewidth. In: Vojt\u00e1\u0161, P., Bielikov\u00e1, M., Charron-Bost, B., S\u00fdkora, O. (eds.) SOFSEM 2005. LNCS, vol.\u00a03381, pp. 1\u201316. Springer, Heidelberg (2005)"},{"key":"6_CR5","doi-asserted-by":"publisher","first-page":"81","DOI":"10.1007\/s00453-007-9056-z","volume":"51","author":"H.L. Bodlaender","year":"2008","unstructured":"Bodlaender, H.L., Grigoriev, A., Arie, M.C., Koster, A.: Treewidth lower bounds with brambles. Algorithmica\u00a051, 81\u201398 (2008)","journal-title":"Algorithmica"},{"issue":"1","key":"6_CR6","doi-asserted-by":"publisher","first-page":"5","DOI":"10.7155\/jgaa.00117","volume":"10","author":"H.L. Bodlaender","year":"2006","unstructured":"Bodlaender, H.L., Koster, A.M.C.A., Wolle, T.: Contraction and treewidth lower bounds. Journal of Graph Algorithms and Applications (JGAA)\u00a010(1), 5\u201349 (2006)","journal-title":"Journal of Graph Algorithms and Applications (JGAA)"},{"key":"6_CR7","unstructured":"van den Broek, J.-W., Bodlaender, H.L.: TreewidthLIB (March 2009), http:\/\/people.cs.uu.nl\/hansb\/treewidthlib\/"},{"key":"6_CR8","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"70","DOI":"10.1007\/3-540-44867-5_6","volume-title":"Experimental and Efficient Algorithms","author":"F. Clautiaux","year":"2003","unstructured":"Clautiaux, F., Carlier, J., Moukrim, A., N\u00e8gre, S.: New lower and upper bounds for graph treewidth. In: Jansen, K., Margraf, M., Mastrolli, M., Rolim, J.D.P. (eds.) WEA 2003. LNCS, vol.\u00a02647, pp. 70\u201380. Springer, Heidelberg (2003)"},{"key":"6_CR9","series-title":"Formal Models and Semantics","first-page":"193","volume-title":"Handbook of Theoretical Computer Science","author":"B. Courcelle","year":"1990","unstructured":"Courcelle, B.: Graph rewriting: An algebraic and logic approach. In: van Leeuwen, J. (ed.) Handbook of Theoretical Computer Science. Formal Models and Semantics, vol.\u00a0B, ch.\u00a05, pp. 193\u2013242. Elsevier, Amsterdam (1990)"},{"key":"6_CR10","doi-asserted-by":"publisher","first-page":"209","DOI":"10.1016\/S1574-6526(06)80011-8","volume-title":"Handbook of Constraint Programming, ch. 7","author":"R. Dechter","year":"2006","unstructured":"Dechter, R.: Tractable structures for constraint satisfaction problems. In: Rossi, F., van Beek, P., Walsh, T. (eds.) Handbook of Constraint Programming, ch. 7, pp. 209\u2013244. Elsevier, Amsterdam (2006)"},{"key":"6_CR11","unstructured":"Gogate, V., Dechter, R.: A complete anytime algorithm for treewidth. In: Proc. of the 20th Conference on Uncertainty in Artificial Intelligence (UAI 2004). ACM International Conference Proceeding Series, vol.\u00a070, pp. 201\u2013208. AUAI Press (2004)"},{"key":"6_CR12","doi-asserted-by":"publisher","first-page":"54","DOI":"10.1016\/S1571-0653(05)80078-2","volume":"8","author":"A.M.C.A. Koster","year":"2001","unstructured":"Koster, A.M.C.A., Bodlaender, H.L., van Hoesel, S.P.M.: Treewidth: Computational experiments. Electronic Notes in Discrete Mathematics\u00a08, 54\u201357 (2001); Extended version available as Technical Report ZIB-Report 01-38, Konrad-Zuse-Zentrum f\u00fcr Informationstechnik Berlin (ZIB)","journal-title":"Electronic Notes in Discrete Mathematics"},{"key":"6_CR13","doi-asserted-by":"publisher","first-page":"309","DOI":"10.1016\/0196-6774(86)90023-4","volume":"7","author":"N. Robertson","year":"1986","unstructured":"Robertson, N., Seymour, P.D.: Graph minors\u00a0II. Algorithmic aspects of tree-width. Journal of Algorithms\u00a07, 309\u2013322 (1986)","journal-title":"Journal of Algorithms"},{"key":"6_CR14","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"827","DOI":"10.1007\/11564751_73","volume-title":"Principles and Practice of Constraint Programming - CP 2005","author":"C. Sinz","year":"2005","unstructured":"Sinz, C.: Towards an optimal CNF encoding of Boolean cardinality constraints. In: van Beek, P. (ed.) CP 2005. LNCS, vol.\u00a03709, pp. 827\u2013831. Springer, Heidelberg (2005)"}],"container-title":["Lecture Notes in Computer Science","Theory and Applications of Satisfiability Testing - SAT 2009"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-642-02777-2_6","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,5,20]],"date-time":"2019-05-20T22:58:06Z","timestamp":1558393086000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-642-02777-2_6"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2009]]},"ISBN":["9783642027765","9783642027772"],"references-count":14,"URL":"https:\/\/doi.org\/10.1007\/978-3-642-02777-2_6","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2009]]}}}