{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,9,6]],"date-time":"2024-09-06T01:17:22Z","timestamp":1725585442512},"publisher-location":"Berlin, Heidelberg","reference-count":17,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783642215803"},{"type":"electronic","value":"9783642215810"}],"license":[{"start":{"date-parts":[[2011,1,1]],"date-time":"2011-01-01T00:00:00Z","timestamp":1293840000000},"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":[[2011]]},"DOI":"10.1007\/978-3-642-21581-0_6","type":"book-chapter","created":{"date-parts":[[2011,6,10]],"date-time":"2011-06-10T09:30:19Z","timestamp":1307698219000},"page":"47-60","source":"Crossref","is-referenced-by-count":2,"title":["Satisfiability of Acyclic and almost Acyclic CNF Formulas (II)"],"prefix":"10.1007","author":[{"given":"Sebastian","family":"Ordyniak","sequence":"first","affiliation":[]},{"given":"Daniel","family":"Paulusma","sequence":"additional","affiliation":[]},{"given":"Stefan","family":"Szeider","sequence":"additional","affiliation":[]}],"member":"297","reference":[{"issue":"1-2","key":"6_CR1","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1016\/S0304-3975(97)00228-4","volume":"209","author":"H.L. Bodlaender","year":"1998","unstructured":"Bodlaender, H.L.: A partial k-arboretum of graphs with bounded treewidth. Theoret. Comput. Sci.\u00a0209(1-2), 1\u201345 (1998)","journal-title":"Theoret. Comput. Sci."},{"key":"6_CR2","series-title":"SIAM Monographs on Discrete Mathematics and Applications","doi-asserted-by":"publisher","DOI":"10.1137\/1.9780898719796","volume-title":"Graph classes: a survey","author":"A. Brandst\u00e4dt","year":"1999","unstructured":"Brandst\u00e4dt, A., Le, V.B., Spinrad, J.P.: Graph classes: a survey. SIAM Monographs on Discrete Mathematics and Applications. SIAM, Philadelphia (1999)"},{"key":"6_CR3","first-page":"273","volume":"67","author":"A. Brandst\u00e4dt","year":"2003","unstructured":"Brandst\u00e4dt, A., Lozin, V.V.: On the linear structure and clique-width of bipartite permutation graphs. Ars Combinatoria\u00a067, 273\u2013281 (2003)","journal-title":"Ars Combinatoria"},{"issue":"1-3","key":"6_CR4","doi-asserted-by":"publisher","first-page":"77","DOI":"10.1016\/S0166-218X(99)00184-5","volume":"101","author":"B. Courcelle","year":"2000","unstructured":"Courcelle, B., Olariu, S.: Upper bounds to the clique-width of graphs. Discr. Appl. Math.\u00a0101(1-3), 77\u2013114 (2000)","journal-title":"Discr. Appl. Math."},{"issue":"3","key":"6_CR5","doi-asserted-by":"publisher","first-page":"201","DOI":"10.1145\/321033.321034","volume":"7","author":"M. Davis","year":"1960","unstructured":"Davis, M., Putnam, H.: A computing procedure for quantification theory. J. ACM\u00a07(3), 201\u2013215 (1960)","journal-title":"J. ACM"},{"issue":"3","key":"6_CR6","doi-asserted-by":"publisher","first-page":"514","DOI":"10.1145\/2402.322390","volume":"30","author":"R. Fagin","year":"1983","unstructured":"Fagin, R.: Degrees of acyclicity for hypergraphs and relational database schemes. J. ACM\u00a030(3), 514\u2013550 (1983)","journal-title":"J. ACM"},{"issue":"4","key":"6_CR7","doi-asserted-by":"publisher","first-page":"511","DOI":"10.1016\/j.dam.2006.06.020","volume":"156","author":"E. Fischer","year":"2008","unstructured":"Fischer, E., Makowsky, J.A., Ravve, E.R.: Counting truth assignments of formulas of bounded tree-width or clique-width. Discr. Appl. Math.\u00a0156(4), 511\u2013529 (2008)","journal-title":"Discr. Appl. Math."},{"unstructured":"Ganian, R., Hlinen\u00fd, P., Obdrz\u00e1lek, J.: Better algorithms for satisfiability problems for formulas of bounded rank-width. In: Lodaya, K., Mahajan, M. (eds.) IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science, FSTTCS 2010, Chennai, India, December 15-18. LIPIcs, vol.\u00a08, pp. 73\u201383. Schloss Dagstuhl - Leibniz-Zentrum fuer Informatik (2010)","key":"6_CR8"},{"issue":"3","key":"6_CR9","doi-asserted-by":"publisher","first-page":"303","DOI":"10.1093\/comjnl\/bxm056","volume":"51","author":"G. Gottlob","year":"2006","unstructured":"Gottlob, G., Szeider, S.: Fixed-parameter algorithms for artificial intelligence, constraint satisfaction, and database problems. The Computer Journal\u00a051(3), 303\u2013325 (2006), Survey paper","journal-title":"The Computer Journal"},{"key":"6_CR10","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"116","DOI":"10.1007\/3-540-56279-6_64","volume-title":"Algorithms and Computation","author":"T. Kloks","year":"1992","unstructured":"Kloks, T., Bodlaender, H.: Approximating treewidth and pathwidth of some classes of perfect graphs. In: Ibaraki, T., Iwama, K., Yamashita, M., Inagaki, Y., Nishizeki, T. (eds.) ISAAC 1992. LNCS, vol.\u00a0650, pp. 116\u2013125. Springer, Heidelberg (1992)"},{"unstructured":"Kullmann, O., Luckhardt, H.: Algorithms for SAT\/TAUT decision based on various measures (1999) (manuscript)","key":"6_CR11"},{"unstructured":"Ordyniak, S., Paulusma, D., Szeider, S.: Satisfiability of acyclic and almost acyclic CNF formulas. In: Lodaya, K., Mahajan, M. (eds.) IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science, FSTTCS 2010, Chennai, India, December 15-18. LIPIcs, vol.\u00a08, pp. 84\u201395. Schloss Dagstuhl - Leibniz-Zentrum fuer Informatik (2010)","key":"6_CR12"},{"issue":"1","key":"6_CR13","doi-asserted-by":"publisher","first-page":"50","DOI":"10.1016\/j.jda.2009.06.002","volume":"8","author":"M. Samer","year":"2010","unstructured":"Samer, M., Szeider, S.: Algorithms for propositional model counting. J. Discrete Algorithms\u00a08(1), 50\u201364 (2010)","journal-title":"J. Discrete Algorithms"},{"issue":"3","key":"6_CR14","doi-asserted-by":"publisher","first-page":"133","DOI":"10.1016\/0020-0190(95)00019-9","volume":"54","author":"J.S. Schlipf","year":"1995","unstructured":"Schlipf, J.S., Annexstein, F.S., Franco, J.V., Swaminathan, R.P.: On finding solutions for extended Horn formulas. Information Processing Letters\u00a054(3), 133\u2013137 (1995)","journal-title":"Information Processing Letters"},{"key":"6_CR15","first-page":"27","volume-title":"Handbook of Satisfiability","author":"E. Speckenmeyer","year":"2009","unstructured":"Speckenmeyer, E.: Classes of easy expressions. In: Biere, A., Heule, M., van Maaren, H., Walsh, T. (eds.) Handbook of Satisfiability, ch. 13, Section 1.19, pp. 27\u201331. IOS Press, Amsterdam (2009)"},{"key":"6_CR16","series-title":"Fields Institute Monographs","doi-asserted-by":"publisher","DOI":"10.1090\/fim\/019","volume-title":"Efficient Graph Representations","author":"J.P. Spinrad","year":"2003","unstructured":"Spinrad, J.P.: Efficient Graph Representations. Fields Institute Monographs. AMS, Providence (2003)"},{"issue":"3","key":"6_CR17","doi-asserted-by":"publisher","first-page":"566","DOI":"10.1137\/0213035","volume":"13","author":"R.E. Tarjan","year":"1984","unstructured":"Tarjan, R.E., Yannakakis, M.: Simple linear-time algorithms to test chordality of graphs, test acyclicity of hypergraphs, and selectively reduce acyclic hypergraphs. SIAM J. Comput.\u00a013(3), 566\u2013579 (1984)","journal-title":"SIAM J. Comput."}],"container-title":["Lecture Notes in Computer Science","Theory and Applications of Satisfiability Testing - SAT 2011"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-642-21581-0_6","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,3,28]],"date-time":"2019-03-28T11:43:58Z","timestamp":1553773438000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-642-21581-0_6"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2011]]},"ISBN":["9783642215803","9783642215810"],"references-count":17,"URL":"https:\/\/doi.org\/10.1007\/978-3-642-21581-0_6","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2011]]}}}