{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,3,26]],"date-time":"2025-03-26T12:11:08Z","timestamp":1742991068328,"version":"3.40.3"},"publisher-location":"Cham","reference-count":31,"publisher":"Springer International Publishing","isbn-type":[{"type":"print","value":"9783319662626"},{"type":"electronic","value":"9783319662633"}],"license":[{"start":{"date-parts":[[2017,1,1]],"date-time":"2017-01-01T00:00:00Z","timestamp":1483228800000},"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":[[2017]]},"DOI":"10.1007\/978-3-319-66263-3_25","type":"book-chapter","created":{"date-parts":[[2017,8,8]],"date-time":"2017-08-08T08:05:11Z","timestamp":1502179511000},"page":"401-411","source":"Crossref","is-referenced-by-count":5,"title":["SAT-Based Local Improvement for Finding Tree Decompositions of Small Width"],"prefix":"10.1007","author":[{"given":"Johannes K.","family":"Fichte","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Neha","family":"Lodha","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Stefan","family":"Szeider","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2017,8,9]]},"reference":[{"key":"25_CR1","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"376","DOI":"10.1007\/978-3-319-59776-8_30","volume-title":"Integration of AI and OR Techniques in Constraint Programming","author":"M Abseher","year":"2017","unstructured":"Abseher, M., Musliu, N., Woltran, S.: htd \u2013 a free, open-source framework for (customized) tree decompositions and beyond. In: Salvagnin, D., Lombardi, M. (eds.) CPAIOR 2017. LNCS, vol. 10335, pp. 376\u2013386. Springer, Cham (2017). doi: 10.1007\/978-3-319-59776-8_30"},{"issue":"2","key":"25_CR2","doi-asserted-by":"crossref","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 J. Algebraic Discrete Methods 8(2), 277\u2013284 (1987)","journal-title":"SIAM J. Algebraic Discrete Methods"},{"key":"25_CR3","unstructured":"Bannach, M., Berndt, S., Ehlers, T.: Jdrasil: a modular library for computing tree decompositions. Technical report, L\u00fcbeck University, Germany (2016)"},{"key":"25_CR4","doi-asserted-by":"crossref","unstructured":"Berg, J., J\u00e4rvisalo, M.: SAT-based approaches to treewidth computation: an evaluation. In: Proceedings of the 26th IEEE International Conference on Tools with Artificial Intelligence, ICTAI 2014, pp. 328\u2013335. IEEE Computer Society, Limassol, Cyprus, November 2014","DOI":"10.1109\/ICTAI.2014.57"},{"issue":"3","key":"25_CR5","doi-asserted-by":"crossref","first-page":"255","DOI":"10.1093\/comjnl\/bxm037","volume":"51","author":"HL Bodlaender","year":"2008","unstructured":"Bodlaender, H.L., Koster, A.M.C.A.: Combinatorial optimization on graphs of bounded treewidth. Comput. J. 51(3), 255\u2013269 (2008)","journal-title":"Comput. J."},{"issue":"3","key":"25_CR6","doi-asserted-by":"crossref","first-page":"259","DOI":"10.1016\/j.ic.2009.03.008","volume":"208","author":"HL Bodlaender","year":"2010","unstructured":"Bodlaender, H.L., Koster, A.M.C.A.: Treewidth computations I. Upper bounds. Inf. Comput. 208(3), 259\u2013275 (2010)","journal-title":"Inf. Comput."},{"key":"25_CR7","unstructured":"van den Broek, J.W., Bodlaender, H.: TreewidthLIB - a benchmark for algorithms for treewidth and related graph problems. Technical report, Faculty of Science, Utrecht University (2010). http:\/\/www.staff.science.uu.nl\/~bodla101\/treewidthlib\/"},{"key":"25_CR8","doi-asserted-by":"crossref","first-page":"67","DOI":"10.1016\/j.jda.2012.04.016","volume":"16","author":"M Chimani","year":"2012","unstructured":"Chimani, M., Mutzel, P., Zey, B.: Improved Steiner tree algorithms for bounded treewidth. J. Discrete Algorithms 16, 67\u201378 (2012)","journal-title":"J. Discrete Algorithms"},{"issue":"1\u20132","key":"25_CR9","doi-asserted-by":"crossref","first-page":"23","DOI":"10.1016\/S0166-218X(00)00221-3","volume":"108","author":"B Courcelle","year":"2001","unstructured":"Courcelle, B., Makowsky, J.A., Rotics, U.: On the fixed parameter complexity of graph enumeration problems definable in monadic second-order logic. Discr. Appl. Math. 108(1\u20132), 23\u201352 (2001)","journal-title":"Discr. Appl. Math."},{"issue":"3","key":"25_CR10","doi-asserted-by":"crossref","first-page":"280","DOI":"10.1145\/765568.765570","volume":"50","author":"A Darwiche","year":"2003","unstructured":"Darwiche, A.: A differential approach to inference in Bayesian networks. J. ACM 50(3), 280\u2013305 (2003)","journal-title":"J. ACM"},{"key":"25_CR11","doi-asserted-by":"crossref","unstructured":"Dechter, R.: Tractable structures for constraint satisfaction problems. In: Rossi, F., van Beek, P., Walsh, T. (eds.) Handbook of Constraint Programming, Chap. 7, vol. I, pp. 209\u2013244. Elsevier, Amsterdam (2006)","DOI":"10.1016\/S1574-6526(06)80011-8"},{"key":"25_CR12","unstructured":"Dechter, R.: Graphical model algorithms at UC Irvine. Technical report, UC Irvine (2013). The network instances consist of Bayesian and Markov network susedin UAI competition and protein folding\/side-chain prediction problems. http:\/\/graphmod.ics.uci.edu\/group"},{"key":"25_CR13","unstructured":"Dell, H., Rosamond, F.: The parameterized algorithms and computational experiments challenge (2016). https:\/\/pacechallenge.wordpress.com\/"},{"key":"25_CR14","unstructured":"Fichte, J.K.: daajoe\/gtfs2graphs - a GTFS transit feed to graph format converter (2016). https:\/\/github.com\/daajoe\/gtfs2graphs"},{"key":"25_CR15","unstructured":"Fichte, J.K., Lodha, N., Szeider, S.: Trellis: treewidth local improvement solver (2017). https:\/\/github.com\/daajoe\/trellis"},{"issue":"4","key":"25_CR16","doi-asserted-by":"crossref","first-page":"755","DOI":"10.1145\/4221.4225","volume":"32","author":"EC Freuder","year":"1985","unstructured":"Freuder, E.C.: A sufficient condition for backtrack-bounded search. J. ACM 32(4), 755\u2013761 (1985)","journal-title":"J. ACM"},{"key":"25_CR17","unstructured":"Gaspers, S., Gudmundsson, J., Jones, M., Mestre, J., R\u00fcmmele, S.: Turbocharging Treewidth Heuristics. In: Guo, J., Hermelin, D. (eds.) 11th International Symposium on Parameterized and Exact Computation (IPEC 2016). Leibniz International Proceedings in Informatics (LIPIcs), vol. 63, pp. 13:1\u201313:13. Schloss Dagstuhl-Leibniz-Zentrum fuer Informatik, Dagstuhl, Germany (2017)"},{"key":"25_CR18","unstructured":"Gogate, V., Dechter, R.: A complete anytime algorithm for treewidth. In: Proceedings of the Twentieth Conference Annual Conference on Uncertainty in Artificial Intelligence (UAI 2004), pp. 201\u2013208. AUAI Press, Arlington (2004)"},{"issue":"1","key":"25_CR19","doi-asserted-by":"crossref","first-page":"105","DOI":"10.1016\/j.artint.2009.10.003","volume":"174","author":"G Gottlob","year":"2010","unstructured":"Gottlob, G., Pichler, R., Wei, F.: Bounded treewidth as a key to tractability of knowledge representation and reasoning. Artif. Intell. 174(1), 105\u2013132 (2010)","journal-title":"Artif. Intell."},{"key":"25_CR20","doi-asserted-by":"publisher","first-page":"1255","DOI":"10.1007\/978-3-662-43505-2_64","volume-title":"Springer Handbook of Computational Intelligence","author":"T Hammerl","year":"2015","unstructured":"Hammerl, T., Musliu, N., Schafhauser, W.: Metaheuristic algorithms and tree decomposition. In: Kacprzyk, J., Pedrycz, W. (eds.) Springer Handbook of Computational Intelligence, pp. 1255\u20131270. Springer, Heidelberg (2015). doi: 10.1007\/978-3-662-43505-2_64"},{"key":"25_CR21","doi-asserted-by":"crossref","unstructured":"Kask, K., Gelfand, A., Otten, L., Dechter, R.: Pushing the power of stochastic greedy ordering schemes for inference in graphical models. In: Burgard, W., Roth, D. (eds.) Proceedings of the Twenty-Fifth AAAI Conference on Artificial Intelligence, AAAI 2011. AAAI Press (2011)","DOI":"10.1609\/aaai.v25i1.7828"},{"key":"25_CR22","unstructured":"Kittan, K.: Zuse cluster (2017). http:\/\/www.cs.uni-potsdam.de\/bs\/research\/labsZuse.html"},{"key":"25_CR23","doi-asserted-by":"crossref","DOI":"10.1007\/BFb0045375","volume-title":"Treewidth: Computations and Approximations","author":"T Kloks","year":"1994","unstructured":"Kloks, T.: Treewidth: Computations and Approximations. Springer, Heidelberg (1994)"},{"issue":"2","key":"25_CR24","doi-asserted-by":"crossref","first-page":"157","DOI":"10.1111\/j.2517-6161.1988.tb01721.x","volume":"50","author":"SL Lauritzen","year":"1988","unstructured":"Lauritzen, S.L., Spiegelhalter, D.J.: Local computations with probabilities on graphical structures and their application to expert systems. J. Roy. Statist. Soc. Ser. B 50(2), 157\u2013224 (1988)","journal-title":"J. Roy. Statist. Soc. Ser. B"},{"key":"25_CR25","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"179","DOI":"10.1007\/978-3-319-40970-2_12","volume-title":"Theory and Applications of Satisfiability Testing \u2013 SAT 2016","author":"N Lodha","year":"2016","unstructured":"Lodha, N., Ordyniak, S., Szeider, S.: A SAT approach to branchwidth. In: Creignou, N., Le Berre, D. (eds.) SAT 2016. LNCS, vol. 9710, pp. 179\u2013195. Springer, Cham (2016). doi: 10.1007\/978-3-319-40970-2_12"},{"key":"25_CR26","doi-asserted-by":"crossref","first-page":"263","DOI":"10.1613\/jair.3744","volume":"46","author":"S Ordyniak","year":"2013","unstructured":"Ordyniak, S., Szeider, S.: Parameterized complexity results for exact Bayesian network structure learning. J. Artif. Intell. Res. 46, 263\u2013302 (2013)","journal-title":"J. Artif. Intell. Res."},{"key":"25_CR27","doi-asserted-by":"crossref","first-page":"139","DOI":"10.3233\/SAT190083","volume":"7","author":"O Roussel","year":"2011","unstructured":"Roussel, O.: Controlling a solver execution with the runsolver tool. J. Satisfiability Boolean Model. Comput. 7, 139\u2013144 (2011)","journal-title":"J. Satisfiability Boolean Model. Comput."},{"key":"25_CR28","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"45","DOI":"10.1007\/978-3-642-02777-2_6","volume-title":"Theory and Applications of Satisfiability Testing - SAT 2009","author":"M Samer","year":"2009","unstructured":"Samer, M., Veith, H.: Encoding treewidth into SAT. In: Kullmann, O. (ed.) SAT 2009. LNCS, vol. 5584, pp. 45\u201350. Springer, Heidelberg (2009). doi: 10.1007\/978-3-642-02777-2_6"},{"key":"25_CR29","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: Beek, P. (ed.) CP 2005. LNCS, vol. 3709, pp. 827\u2013831. Springer, Heidelberg (2005). doi: 10.1007\/11564751_73"},{"key":"25_CR30","doi-asserted-by":"crossref","unstructured":"Song, Y., Liu, C., Malmberg, R.L., Pan, F., Cai, L.: Tree decomposition based fast search of RNA structures including pseudoknots in genomes. In: Proceedings of the 4th International IEEE Computer Society Computational Systems Bioinformatics Conference, CSB 2005, pp. 223\u2013234. IEEE Computer Society (2005)","DOI":"10.1109\/CSB.2005.52"},{"key":"25_CR31","unstructured":"Tamaki, H.: TCS-Meiji (2016). https:\/\/github.com\/TCS-Meiji\/treewidth-exact"}],"container-title":["Lecture Notes in Computer Science","Theory and Applications of Satisfiability Testing \u2013 SAT 2017"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-319-66263-3_25","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2024,6,26]],"date-time":"2024-06-26T01:39:47Z","timestamp":1719365987000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-319-66263-3_25"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2017]]},"ISBN":["9783319662626","9783319662633"],"references-count":31,"URL":"https:\/\/doi.org\/10.1007\/978-3-319-66263-3_25","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2017]]}}}