{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,9,9]],"date-time":"2024-09-09T04:46:49Z","timestamp":1725857209276},"publisher-location":"Cham","reference-count":21,"publisher":"Springer International Publishing","isbn-type":[{"type":"print","value":"9783319409696"},{"type":"electronic","value":"9783319409702"}],"license":[{"start":{"date-parts":[[2016,1,1]],"date-time":"2016-01-01T00:00:00Z","timestamp":1451606400000},"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":[[2016]]},"DOI":"10.1007\/978-3-319-40970-2_12","type":"book-chapter","created":{"date-parts":[[2016,6,10]],"date-time":"2016-06-10T07:14:55Z","timestamp":1465542895000},"page":"179-195","source":"Crossref","is-referenced-by-count":7,"title":["A SAT Approach to Branchwidth"],"prefix":"10.1007","author":[{"given":"Neha","family":"Lodha","sequence":"first","affiliation":[]},{"given":"Sebastian","family":"Ordyniak","sequence":"additional","affiliation":[]},{"given":"Stefan","family":"Szeider","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2016,6,11]]},"reference":[{"key":"12_CR1","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"crossref","first-page":"159","DOI":"10.1007\/978-3-642-16926-7_16","volume-title":"Graph Theoretic Concepts in Computer Science","author":"I Adler","year":"2010","unstructured":"Adler, I., Bui-Xuan, B.-M., Rabinovich, Y., Renault, G., Telle, J.A., Vatshelle, M.: On the boolean-width of a graph: structure and applications. In: Thilikos, D.M. (ed.) WG 2010. LNCS, vol. 6410, pp. 159\u2013170. Springer, Heidelberg (2010)"},{"key":"12_CR2","doi-asserted-by":"crossref","unstructured":"Alekhnovich, M., Razborov, A.A.: Satisfiability, branch-width and Tseitin tautologies. In: Proceedings of the 43rd Annual IEEE Symposium on Foundations of Computer Science (FOCS 2002), pp. 593\u2013603 (2002)","DOI":"10.1109\/SFCS.2002.1181983"},{"key":"12_CR3","doi-asserted-by":"crossref","unstructured":"Bacchus, F., Dalmao, S., Pitassi, T.: Algorithms and complexity results for #SAT and Bayesian inference. In: 44th Annual IEEE Symposium on Foundations of Computer Science (FOCS 2003), pp. 340\u2013351 (2003)","DOI":"10.1109\/SFCS.2003.1238208"},{"key":"12_CR4","doi-asserted-by":"crossref","unstructured":"Berg, J., J\u00e4rvisalo, M.: SAT-based approaches to treewidth computation: an evaluation. In: 26th IEEE International Conference on Tools with Artificial Intelligence, ICTAI 2014, Limassol, Cyprus, 10\u201312 November 2014, pp. 328\u2013335. IEEE Computer Society (2014)","DOI":"10.1109\/ICTAI.2014.57"},{"key":"12_CR5","unstructured":"Bodlander, H.: TreewidthLIB a benchmark for algorithms for treewidth and related graph problems. http:\/\/www.staff.science.uu.nl\/~bodla101\/treewidthlib\/"},{"issue":"3","key":"12_CR6","doi-asserted-by":"crossref","first-page":"233","DOI":"10.1287\/ijoc.15.3.233.16078","volume":"15","author":"W Cook","year":"2003","unstructured":"Cook, W., Seymour, P.: Tour merging via branch-decomposition. INFORMS J. Comput. 15(3), 233\u2013248 (2003)","journal-title":"INFORMS J. Comput."},{"key":"12_CR7","doi-asserted-by":"crossref","unstructured":"Cornu\u00e9jols, G.: Combinatorial Optimization: Packing and Covering. Regional Conference Series in Applied Mathematics. Society for Industrial and Applied Mathematics, Carnegie Mellon University, Pittsburgh, Pennsylvania (2001)","DOI":"10.1137\/1.9780898717105"},{"key":"12_CR8","series-title":"Graduate Texts in Mathematics","volume-title":"Graph Theory","author":"R Diestel","year":"2000","unstructured":"Diestel, R.: Graph Theory. Graduate Texts in Mathematics, vol. 173, 2nd edn. Springer, New York (2000)","edition":"2"},{"issue":"12","key":"12_CR9","doi-asserted-by":"crossref","first-page":"2726","DOI":"10.1016\/j.dam.2008.08.009","volume":"157","author":"FV Fomin","year":"2009","unstructured":"Fomin, F.V., Mazoit, F., Todinca, I.: Computing branchwidth via efficient triangulations and blocks. Discr. Appl. Math. 157(12), 2726\u20132736 (2009)","journal-title":"Discr. Appl. Math."},{"key":"12_CR10","unstructured":"Grohe, M.: Logic, graphs, and algorithms. In: Flum, J., Gr\u00e4del, E., Wilke, T. (eds.) Logic and Automata: History and Perspectives. Texts in Logic and Games, vol. 2, pp. 357\u2013422. Amsterdam University Press (2008)"},{"key":"12_CR11","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"crossref","first-page":"318","DOI":"10.1007\/978-3-642-39071-5_24","volume-title":"Theory and Applications of Satisfiability Testing \u2013 SAT 2013","author":"MJH Heule","year":"2013","unstructured":"Heule, M.J.H., Szeider, S.: A SAT approach to clique-width. In: J\u00e4rvisalo, M., Van Gelder, A. (eds.) SAT 2013. LNCS, vol. 7962, pp. 318\u2013334. Springer, Heidelberg (2013)"},{"key":"12_CR12","doi-asserted-by":"crossref","unstructured":"Hicks, I.V.: Graphs, branchwidth, and tangles! Oh my! Networks 45(2), 55\u201360 (2005)","DOI":"10.1002\/net.20050"},{"key":"12_CR13","first-page":"31","volume":"159","author":"IV Hicks","year":"2002","unstructured":"Hicks, I.V.: Branchwidth heuristics. Congr. Numer. 159, 31\u201350 (2002)","journal-title":"Congr. Numer."},{"issue":"3","key":"12_CR14","doi-asserted-by":"crossref","first-page":"1012","DOI":"10.1137\/070685920","volume":"38","author":"P Hlin\u011bn\u00fd","year":"2008","unstructured":"Hlin\u011bn\u00fd, P., Oum, S.: Finding branch-decompositions and rank-decompositions. SIAM J. Comput. 38(3), 1012\u20131032 (2008)","journal-title":"SIAM J. Comput."},{"key":"12_CR15","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, San Francisco, California, USA, 7\u201311 August 2011. AAAI Press (2011)"},{"key":"12_CR16","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"crossref","first-page":"444","DOI":"10.1007\/978-3-642-18381-2_37","volume-title":"SOFSEM 2011: Theory and Practice of Computer Science","author":"A Overwijk","year":"2011","unstructured":"Overwijk, A., Penninkx, E., Bodlaender, H.L.: A local search algorithm for branchwidth. In: \u010cern\u00e1, I., Gyim\u00f3thy, T., Hromkovi\u010d, J., Jefferey, K., Kr\u00e1lovi\u0107, R., Vukoli\u0107, M., Wolf, S. (eds.) SOFSEM 2011. LNCS, vol. 6543, pp. 444\u2013454. Springer, Heidelberg (2011)"},{"issue":"2","key":"12_CR17","doi-asserted-by":"crossref","first-page":"153","DOI":"10.1016\/0095-8956(91)90061-N","volume":"52","author":"N Robertson","year":"1991","unstructured":"Robertson, N., Seymour, P.D.: Graph minors X. Obstructions to tree-decomposition. J. Combin. Theory Ser. B 52(2), 153\u2013190 (1991)","journal-title":"J. Combin. Theory Ser. B"},{"key":"12_CR18","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"crossref","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)"},{"issue":"2","key":"12_CR19","doi-asserted-by":"crossref","first-page":"217","DOI":"10.1007\/BF01215352","volume":"14","author":"PD Seymour","year":"1994","unstructured":"Seymour, P.D., Thomas, R.: Call routing and the ratcatcher. Combinatorica 14(2), 217\u2013241 (1994)","journal-title":"Combinatorica"},{"key":"12_CR20","unstructured":"Ulusal, E.: Integer Programming Models for the Branchwidth Problem. Ph.D. thesis, Texas A&M University, May 2008"},{"key":"12_CR21","unstructured":"Weisstein, E.: MathWorld online mathematics resource. http:\/\/mathworld.wolfram.com"}],"container-title":["Lecture Notes in Computer Science","Theory and Applications of Satisfiability Testing \u2013 SAT 2016"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-319-40970-2_12","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2017,6,24]],"date-time":"2017-06-24T12:06:03Z","timestamp":1498305963000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-319-40970-2_12"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2016]]},"ISBN":["9783319409696","9783319409702"],"references-count":21,"URL":"https:\/\/doi.org\/10.1007\/978-3-319-40970-2_12","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2016]]}}}