{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,1,30]],"date-time":"2025-01-30T06:20:15Z","timestamp":1738218015936,"version":"3.34.0"},"publisher-location":"Berlin, Heidelberg","reference-count":34,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783540797180"},{"type":"electronic","value":"9783540797197"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"DOI":"10.1007\/978-3-540-79719-7_10","type":"book-chapter","created":{"date-parts":[[2008,5,6]],"date-time":"2008-05-06T08:04:57Z","timestamp":1210061097000},"page":"105-118","source":"Crossref","is-referenced-by-count":7,"title":["Complexity and Algorithms for Well-Structured k-SAT Instances"],"prefix":"10.1007","author":[{"given":"Konstantinos","family":"Georgiou","sequence":"first","affiliation":[]},{"given":"Periklis A.","family":"Papakonstantinou","sequence":"additional","affiliation":[]}],"member":"297","reference":[{"key":"10_CR1","doi-asserted-by":"crossref","unstructured":"Alekhnovich, A., Razborov, A.: Satisfiability, branch-width and Tseitin tautologies. In: FOCS, pp. 593\u2013603 (2002)","DOI":"10.1109\/SFCS.2002.1181983"},{"key":"10_CR2","doi-asserted-by":"crossref","unstructured":"Amir, E., Mcilraith, S.: Solving satisfiability using decomposition and the most constrained subproblem. In: LICS workshop on Theory and Applications of Satisfiability Testing. Electronic Notes in Discrete Mathematics (2001)","DOI":"10.1016\/S1571-0653(04)00331-2"},{"key":"10_CR3","doi-asserted-by":"publisher","first-page":"70","DOI":"10.1145\/273865.273901","volume":"45","author":"S. Arora","year":"1998","unstructured":"Arora, S., Safra, S.: Probabilistic checking of proofs: A new characterization of NP. J. ACM\u00a045, 70\u2013122 (1998)","journal-title":"J. ACM"},{"key":"10_CR4","doi-asserted-by":"crossref","unstructured":"Bacchus, F., Dalmao, S., Pitassi, T.: Algorithms and complexity results for #SAT and bayesian inference. In: FOCS, pp. 340\u2013351 (2003)","DOI":"10.1109\/SFCS.2003.1238208"},{"issue":"1-2","key":"10_CR5","first-page":"1","volume":"11","author":"H.L. Bodlaender","year":"1993","unstructured":"Bodlaender, H.L.: A tourist guide through treewidth. Acta Cybernet\u00a011(1-2), 1\u201321 (1993)","journal-title":"Acta Cybernet"},{"issue":"2","key":"10_CR6","doi-asserted-by":"publisher","first-page":"238","DOI":"10.1006\/jagm.1995.1009","volume":"18","author":"H.L. Bodlaender","year":"1995","unstructured":"Bodlaender, H.L., Gilbert, J.R., Hafsteinsson, H., Kloks, T.: Approximating treewidth, pathwidth, frontsize, and shortest elimination tree. J. Algorithms\u00a018(2), 238\u2013255 (1995)","journal-title":"J. Algorithms"},{"issue":"3","key":"10_CR7","doi-asserted-by":"publisher","first-page":"223","DOI":"10.1002\/jgt.3190060302","volume":"6","author":"P.Z. Chinn","year":"1982","unstructured":"Chinn, P.Z., Chv\u00e1talov\u00e1, J., Dewdney, A.K., Gibbs, N.E.: The bandwidth problem for graphs and matrices - A survey. J. Graph Theory\u00a06(3), 223\u2013254 (1982)","journal-title":"J. Graph Theory"},{"issue":"1","key":"10_CR8","doi-asserted-by":"publisher","first-page":"4","DOI":"10.1145\/321623.321625","volume":"18","author":"S.A. Cook","year":"1971","unstructured":"Cook, S.A.: Characterizations of pushdown machines in terms of time-bounded computers. J. ACM\u00a018(1), 4\u201318 (1971)","journal-title":"J. ACM"},{"key":"10_CR9","doi-asserted-by":"crossref","unstructured":"Cook, S.A.: The complexity of theorem-proving procedures. In: STOC, pp. 151\u2013158 (1971)","DOI":"10.1145\/800157.805047"},{"issue":"1-2","key":"10_CR10","doi-asserted-by":"publisher","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. Discrete Appl. Math.\u00a0108(1-2), 23\u201352 (2001)","journal-title":"Discrete Appl. Math."},{"key":"10_CR11","volume-title":"Theory of Computational Complexity","author":"D.-Z. Du","year":"2000","unstructured":"Du, D.-Z., Ko, K.-I.: Theory of Computational Complexity. Wiley-Interscience, New York (2000)"},{"issue":"3","key":"10_CR12","doi-asserted-by":"publisher","first-page":"510","DOI":"10.1006\/jcss.1999.1682","volume":"60","author":"U. Feige","year":"2000","unstructured":"Feige, U.: Approximating the bandwidth via volume respecting embeddings. J. Comput. Syst. Sci\u00a060(3), 510\u2013539 (2000)","journal-title":"J. Comput. Syst. Sci"},{"issue":"14","key":"10_CR13","doi-asserted-by":"publisher","first-page":"1885","DOI":"10.1016\/j.dam.2007.03.014","volume":"155","author":"E. Fischer","year":"2007","unstructured":"Fischer, E., Makowsky, J.A., Ravve, E.R.: Counting truth assignments of formulas of bounded tree-width or clique-width. Discrete Appl. Math.\u00a0155(14), 1885\u20131893 (2007)","journal-title":"Discrete Appl. Math."},{"key":"10_CR14","unstructured":"Flouris, M., Lau, L.C., Morioka, T., Papakonstantinou, P.A., Penn, G.: Bounded and ordered satisfiability: connecting recognition with Lambek-style calculi to classical satisfiability testing. In: Math. of language 8, pp. 45\u201356 (2003)"},{"issue":"3","key":"10_CR15","doi-asserted-by":"publisher","first-page":"477","DOI":"10.1137\/0134037","volume":"34","author":"M.R. Garey","year":"1978","unstructured":"Garey, M.R., Graham, R.L., Johnson, D.S., Knuth, D.E.: Complexity results for bandwidth minimization. SIAM J. Appl. Math.\u00a034(3), 477\u2013495 (1978)","journal-title":"SIAM J. Appl. Math."},{"issue":"1\u20132","key":"10_CR16","doi-asserted-by":"publisher","first-page":"55","DOI":"10.1016\/S0004-3702(02)00182-0","volume":"138","author":"G. Gottlob","year":"2002","unstructured":"Gottlob, G., Scarcello, F., Sideri, M.: Fixed-parameter complexity in AI and nonmonotonic reasoning. Artificial Intelligence\u00a0138(1\u20132), 55\u201386 (2002)","journal-title":"Artificial Intelligence"},{"key":"10_CR17","first-page":"216","volume":"8","author":"P. Hlineny","year":"2007","unstructured":"Hlineny, P., Oum, S., Seese, D., Gottlob, G.: Width parameters beyond tree-width and their applications. The Computer Journal\u00a08, 216\u2013235 (2007)","journal-title":"The Computer Journal"},{"key":"10_CR18","first-page":"329","volume-title":"STOC","author":"S. Khanna","year":"1996","unstructured":"Khanna, S., Motwani, R.: Towards a syntactic characterization of PTAS. In: STOC, pp. 329\u2013337. ACM, New York (1996)"},{"issue":"3","key":"10_CR19","doi-asserted-by":"publisher","first-page":"615","DOI":"10.1137\/0209046","volume":"9","author":"R.J. Lipton","year":"1980","unstructured":"Lipton, R.J., Tarjan, R.E.: Applications of a planar separator theorem. SIAM J. of Comp.\u00a09(3), 615\u2013627 (1980)","journal-title":"SIAM J. of Comp."},{"key":"10_CR20","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"396","DOI":"10.1007\/11814948_36","volume-title":"Theory and Applications of Satisfiability Testing - SAT 2006","author":"N. Nishimura","year":"2006","unstructured":"Nishimura, N., Ragde, P., Szeider, S.: Solving #SAT using vertex covers. In: Biere, A., Gomes, C.P. (eds.) SAT 2006. LNCS, vol.\u00a04121, pp. 396\u2013409. Springer, Heidelberg (2006)"},{"issue":"4","key":"10_CR21","doi-asserted-by":"publisher","first-page":"514","DOI":"10.1016\/j.jctb.2005.10.006","volume":"96","author":"S. Oum","year":"2006","unstructured":"Oum, S., Seymour, P.: Approximating clique-width and branch-width. J. Combin. Theory Ser. B\u00a096(4), 514\u2013528 (2006)","journal-title":"J. Combin. Theory Ser. B"},{"issue":"3","key":"10_CR22","doi-asserted-by":"publisher","first-page":"263","DOI":"10.1007\/BF02280884","volume":"16","author":"C.H. Papadimitriou","year":"1976","unstructured":"Papadimitriou, C.H.: The NP-completeness of the bandwidth minimization problem. Computing\u00a016(3), 263\u2013270 (1976)","journal-title":"Computing"},{"key":"10_CR23","unstructured":"Papakonstantinou, P.A., Penn, G., Vahlis, Y.: Polynomial-time and parallel algorithms for fragments of Lambek Grammars (unpublished manuscript)"},{"key":"10_CR24","doi-asserted-by":"publisher","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. of Comb. Theory (Ser. B)\u00a035, 39\u201361 (1983)","journal-title":"J. of Comb. Theory (Ser. B)"},{"key":"10_CR25","doi-asserted-by":"publisher","first-page":"309","DOI":"10.1016\/0196-6774(86)90023-4","volume":"7","author":"N. Robertson","year":"1986","unstructured":"Robertson, N., Seymour, P.D.: Graph minors. II. algorithmic aspects of tree-width. J. of Algorithms\u00a07, 309\u2013322 (1986)","journal-title":"J. of Algorithms"},{"issue":"3","key":"10_CR26","doi-asserted-by":"publisher","first-page":"365","DOI":"10.1016\/0022-0000(81)90038-6","volume":"22","author":"W.L. Ruzzo","year":"1981","unstructured":"Ruzzo, W.L.: On uniform circuit complexity. J. Comput. System Sci.\u00a022(3), 365\u2013383 (1981) Special issue dedicated to Michael Machtey","journal-title":"J. Comput. System Sci."},{"key":"10_CR27","unstructured":"Samer, M., Szeider, S.: A fixed-parameter algorithm for #SAT with parameter incidence treewidth. CoRR, abs\/cs\/061017 (2006) informal publication"},{"key":"10_CR28","series-title":"Lecture Notes in Artificial Intelligence","doi-asserted-by":"publisher","first-page":"484","DOI":"10.1007\/978-3-540-75560-9_35","volume-title":"Logic for Programming, Artificial Intelligence, and Reasoning","author":"M. Samer","year":"2007","unstructured":"Samer, M., Szeider, S.: Algorithms for propositional model counting. In: Dershowitz, N., Voronkov, A. (eds.) LPAR 2007. LNCS (LNAI), vol.\u00a04790, pp. 484\u2013498. Springer, Heidelberg (2007)"},{"issue":"1-3","key":"10_CR29","doi-asserted-by":"publisher","first-page":"203","DOI":"10.1016\/0012-365X(93)E0219-T","volume":"142","author":"L. Smithline","year":"1995","unstructured":"Smithline, L.: Bandwidth of the complete k-ary tree. Discrete Math.\u00a0142(1-3), 203\u2013212 (1995)","journal-title":"Discrete Math."},{"issue":"3","key":"10_CR30","doi-asserted-by":"crossref","first-page":"405","DOI":"10.1145\/322077.322083","volume":"25","author":"I.H. Sudborough","year":"1978","unstructured":"Sudborough, I.H.: On the tape complexity of deterministic context-free languages. J. Assoc. Comput. Mach.\u00a025(3), 405\u2013414 (1978)","journal-title":"J. Assoc. Comput. Mach."},{"key":"10_CR31","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"crossref","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)"},{"issue":"2","key":"10_CR32","doi-asserted-by":"publisher","first-page":"189","DOI":"10.1016\/0304-3975(79)90044-6","volume":"8","author":"L.G. Valiant","year":"1979","unstructured":"Valiant, L.G.: The complexity of computing the permanent. Theoret. Comput. Sci.\u00a08(2), 189\u2013201 (1979)","journal-title":"Theoret. Comput. Sci."},{"issue":"4","key":"10_CR33","doi-asserted-by":"publisher","first-page":"641","DOI":"10.1137\/0212043","volume":"12","author":"L.G. Valiant","year":"1983","unstructured":"Valiant, L.G., Skyum, S., Berkowitz, S., Rackoff, C.: Fast parallel computation of polynomials using few processors. SIAM J. Comput.\u00a012(4), 641\u2013644 (1983)","journal-title":"SIAM J. Comput."},{"key":"10_CR34","doi-asserted-by":"crossref","DOI":"10.1007\/978-3-662-03927-4","volume-title":"Introduction to Circuit Complexity - A Uniform Approach","author":"H. Vollmer","year":"1999","unstructured":"Vollmer, H.: Introduction to Circuit Complexity - A Uniform Approach. Springer, Heidelberg (1999)"}],"container-title":["Lecture Notes in Computer Science","Theory and Applications of Satisfiability Testing \u2013 SAT 2008"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-540-79719-7_10.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,1,30]],"date-time":"2025-01-30T02:37:26Z","timestamp":1738204646000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-540-79719-7_10"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[null]]},"ISBN":["9783540797180","9783540797197"],"references-count":34,"URL":"https:\/\/doi.org\/10.1007\/978-3-540-79719-7_10","relation":{},"subject":[]}}