{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,3,27]],"date-time":"2025-03-27T04:24:10Z","timestamp":1743049450670,"version":"3.40.3"},"publisher-location":"Berlin, Heidelberg","reference-count":13,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783642296994"},{"type":"electronic","value":"9783642297007"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2012]]},"DOI":"10.1007\/978-3-642-29700-7_18","type":"book-chapter","created":{"date-parts":[[2012,4,28]],"date-time":"2012-04-28T12:25:56Z","timestamp":1335615956000},"page":"192-198","source":"Crossref","is-referenced-by-count":0,"title":["Some Remarks on the Incompressibility of Width-Parameterized SAT Instances"],"prefix":"10.1007","author":[{"given":"Bangsheng","family":"Tang","sequence":"first","affiliation":[]}],"member":"297","reference":[{"key":"18_CR1","doi-asserted-by":"crossref","unstructured":"Alekhnovich, M., Razborov, A.A.: Satisfiability, branch-width and Tseitin tautologies. In: Foundations of Computer Science (FOCS), pp. 593\u2013603. IEEE (2002)","DOI":"10.1109\/SFCS.2002.1181983"},{"key":"18_CR2","unstructured":"Allender, E., Chen, S., Lou, T., Papakonstantinou, P., Tang, B.: Width-parameterized sat: Time-space tradeoffs (2012) (manuscript)"},{"issue":"1-2","key":"18_CR3","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. Theoretical Computer Science\u00a0209(1-2), 1\u201345 (1998)","journal-title":"Theoretical Computer Science"},{"key":"18_CR4","doi-asserted-by":"crossref","unstructured":"Dell, H., van Melkebeek, D.: Satisfiability allows no nontrivial sparsification unless the polynomial-time hierarchy collapses. In: Symposium on Theory of Computing (STOC), pp. 251\u2013260. ACM (2010)","DOI":"10.1145\/1806689.1806725"},{"issue":"4","key":"18_CR5","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.V.: Counting truth assignments of formulas of bounded tree-width or clique-width. Discrete Applied Mathematics\u00a0156(4), 511\u2013529 (2008)","journal-title":"Discrete Applied Mathematics"},{"key":"18_CR6","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"105","DOI":"10.1007\/978-3-540-79719-7_10","volume-title":"Theory and Applications of Satisfiability Testing \u2013 SAT 2008","author":"K. Georgiou","year":"2008","unstructured":"Georgiou, K., Papakonstantinou, P.A.: Complexity and Algorithms for Well-Structured k-SAT Instances. In: Kleine B\u00fcning, H., Zhao, X. (eds.) SAT 2008. LNCS, vol.\u00a04996, pp. 105\u2013118. Springer, Heidelberg (2008)"},{"key":"18_CR7","doi-asserted-by":"crossref","unstructured":"Impagliazzo, R., Paturi, R.: Complexity of k-sat. In: Proceedings of Fourteenth Annual IEEE Conference on Computational Complexity, pp. 237\u2013240. IEEE (1999)","DOI":"10.1109\/CCC.1999.766282"},{"issue":"4","key":"18_CR8","doi-asserted-by":"publisher","first-page":"512","DOI":"10.1006\/jcss.2001.1774","volume":"63","author":"R. Impagliazzo","year":"2001","unstructured":"Impagliazzo, R., Paturi, R., Zane, F.: Which problems have strongly exponential complexity? Journal of Computer and System Sciences (JCSS)\u00a063(4), 512\u2013530 (2001); (also FOCS 1998)","journal-title":"Journal of Computer and System Sciences (JCSS)"},{"key":"18_CR9","doi-asserted-by":"crossref","unstructured":"Kloks, T.: Treewidth: computations and approximations, vol.\u00a0842. Springer (1994)","DOI":"10.1007\/BFb0045375"},{"key":"18_CR10","doi-asserted-by":"crossref","unstructured":"Lokshtanov, D., Marx, D., Saurabh, S.: Known algorithms on graphs of bounded treewidth are probably optimal. In: 22nd ACM\/SIAM Symposium on Discrete Algorithms (SODA 2011), pp. 777\u2013789 (2011)","DOI":"10.1137\/1.9781611973082.61"},{"issue":"1","key":"18_CR11","doi-asserted-by":"publisher","first-page":"8","DOI":"10.1016\/j.ipl.2009.09.012","volume":"110","author":"P.A. Papakonstantinou","year":"2009","unstructured":"Papakonstantinou, P.A.: A note on width-parameterized sat: An exact machine-model characterization. Information Processing Letters (IPL)\u00a0110(1), 8\u201312 (2009)","journal-title":"Information Processing Letters (IPL)"},{"key":"18_CR12","unstructured":"Samer, M., Szeider, S.: A fixed-parameter algorithm for# sat with parameter incidence treewidth. Arxiv preprint cs\/0610174 (2006)"},{"key":"18_CR13","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"188","DOI":"10.1007\/978-3-540-24605-3_15","volume-title":"Theory and Applications of Satisfiability Testing","author":"S. Szeider","year":"2004","unstructured":"Szeider, S.: On Fixed-Parameter Tractable Parameterizations of SAT. In: Giunchiglia, E., Tacchella, A. (eds.) SAT 2003. LNCS, vol.\u00a02919, pp. 188\u2013202. Springer, Heidelberg (2004)"}],"container-title":["Lecture Notes in Computer Science","Frontiers in Algorithmics and Algorithmic Aspects in Information and Management"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-642-29700-7_18.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,3,26]],"date-time":"2025-03-26T21:54:27Z","timestamp":1743026067000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-642-29700-7_18"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2012]]},"ISBN":["9783642296994","9783642297007"],"references-count":13,"URL":"https:\/\/doi.org\/10.1007\/978-3-642-29700-7_18","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2012]]}}}