{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,3,28]],"date-time":"2025-03-28T08:46:25Z","timestamp":1743151585900,"version":"3.40.3"},"publisher-location":"Cham","reference-count":17,"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_27","type":"book-chapter","created":{"date-parts":[[2017,8,8]],"date-time":"2017-08-08T04:05:11Z","timestamp":1502165111000},"page":"429-445","source":"Crossref","is-referenced-by-count":6,"title":["SAT-Encodings for Special Treewidth and Pathwidth"],"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":[[2017,8,9]]},"reference":[{"issue":"2","key":"27_CR1","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 \n            $$k$$\n          -tree. SIAM J. Algebr. Discret. Method. 8(2), 277\u2013284 (1987)","journal-title":"SIAM J. Algebr. Discret. Method."},{"key":"27_CR2","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":"27_CR3","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"460","DOI":"10.1007\/978-3-319-03841-4_40","volume-title":"Graph Drawing","author":"T Biedl","year":"2013","unstructured":"Biedl, T., Bl\u00e4sius, T., Niedermann, B., N\u00f6llenburg, M., Prutkin, R., Rutter, I.: Using ILP\/SAT to determine pathwidth, visibility representations, and other grid-based graph drawings. In: Wismath, S., Wolff, A. (eds.) GD 2013. LNCS, vol. 8242, pp. 460\u2013471. Springer, Cham (2013). doi:\n10.1007\/978-3-319-03841-4_40"},{"key":"27_CR4","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"88","DOI":"10.1007\/978-3-642-45043-3_9","volume-title":"Graph-Theoretic Concepts in Computer Science","author":"HL Bodlaender","year":"2013","unstructured":"Bodlaender, H.L., Kratsch, S., Kreuzen, V.J.C.: Fixed-parameter tractability and characterizations of small special treewidth. In: Brandst\u00e4dt, A., Jansen, K., Reischuk, R. (eds.) WG 2013. LNCS, vol. 8165, pp. 88\u201399. Springer, Heidelberg (2013). doi:\n10.1007\/978-3-642-45043-3_9"},{"key":"27_CR5","doi-asserted-by":"crossref","first-page":"29","DOI":"10.1016\/j.dam.2015.01.015","volume":"216","author":"HL Bodlaender","year":"2017","unstructured":"Bodlaender, H.L., Kratsch, S., Kreuzen, V.J., Kwon, O.J., Ok, S.: Characterizing width two for variants of treewidth (part 1). Discr. Appl. Math. 216, 29\u201346 (2017)","journal-title":"Discr. Appl. Math."},{"key":"27_CR6","unstructured":"Courcelle, B.: Special tree-width and the verification of monadic second-order graph properties. In: Lodaya, K., Mahajan, M. (eds) 2010 IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science, FSTTCS, LIPIcs, Chennai, India, vol. 8, pp. 13\u201329. Schloss Dagstuhl - Leibniz-Zentrum fuer Informatik, 15\u201318 Dec 2010"},{"issue":"6","key":"27_CR7","doi-asserted-by":"crossref","first-page":"866","DOI":"10.1016\/j.dam.2010.12.017","volume":"160","author":"B Courcelle","year":"2012","unstructured":"Courcelle, B.: On the model-checking of monadic second-order formulas with edge set quantifications. Discr. Appl. Math. 160(6), 866\u2013887 (2012)","journal-title":"Discr. Appl. Math."},{"key":"27_CR8","unstructured":"Dell, H., Rosamond, F.: The 1st parameterized algorithms and computational experiments challenge\u2013track A: Treewidth. Technical report (2016). \nhttps:\/\/pacechallenge.wordpress.com\/2016\/09\/12\/here-are-the-results-of-the-1st-pace-challenge\/"},{"key":"27_CR9","volume-title":"Graph Theory: Graduate Texts in Mathematics","author":"R Diestel","year":"2000","unstructured":"Diestel, R.: Graph Theory: Graduate Texts in Mathematics, 2nd edn. Springer Verlag, New York (2000)","edition":"2"},{"key":"27_CR10","doi-asserted-by":"crossref","first-page":"47","DOI":"10.1007\/BF01462229","volume":"1","author":"M Habib","year":"1994","unstructured":"Habib, M., M\u00f6hring, R.H.: Treewidth of cocomparability graphs and a new order-theoretic parameter. Order 1, 47\u201360 (1994)","journal-title":"Order"},{"issue":"3","key":"27_CR11","doi-asserted-by":"crossref","first-page":"24","DOI":"10.1145\/2736696","volume":"16","author":"M Heule","year":"2015","unstructured":"Heule, M., Szeider, S.: A SAT approach to clique-width. ACM Trans. Comput. Log. 16(3), 24 (2015)","journal-title":"ACM Trans. Comput. Log."},{"issue":"6","key":"27_CR12","doi-asserted-by":"crossref","first-page":"345","DOI":"10.1016\/0020-0190(92)90234-M","volume":"42","author":"NG Kinnersley","year":"1992","unstructured":"Kinnersley, N.G.: The vertex separation number of a graph equals its path-width. Inf. Process. Lett. 42(6), 345\u2013350 (1992)","journal-title":"Inf. Process. Lett."},{"key":"27_CR13","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 Verlag, Berlin (1994)"},{"key":"27_CR14","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:\n10.1007\/978-3-319-40970-2_12"},{"issue":"1","key":"27_CR15","doi-asserted-by":"crossref","first-page":"39","DOI":"10.1016\/0095-8956(83)90079-5","volume":"35","author":"N Robertson","year":"1983","unstructured":"Robertson, N., Seymour, P.D.: Graph minors. I. excluding a forest. J. Combin. Theory Ser. B 35(1), 39\u201361 (1983)","journal-title":"J. Combin. Theory Ser. B"},{"key":"27_CR16","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:\n10.1007\/978-3-642-02777-2_6"},{"key":"27_CR17","unstructured":"Weisstein, E.: MathWorld online mathematics resource (2016). \nhttp:\/\/mathworld.wolfram.com"}],"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_27","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2017,8,8]],"date-time":"2017-08-08T14:51:25Z","timestamp":1502203885000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-319-66263-3_27"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2017]]},"ISBN":["9783319662626","9783319662633"],"references-count":17,"URL":"https:\/\/doi.org\/10.1007\/978-3-319-66263-3_27","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2017]]}}}