{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,10,9]],"date-time":"2025-10-09T06:33:08Z","timestamp":1759991588144},"publisher-location":"Berlin, Heidelberg","reference-count":31,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783540208518"},{"type":"electronic","value":"9783540246053"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2004]]},"DOI":"10.1007\/978-3-540-24605-3_15","type":"book-chapter","created":{"date-parts":[[2010,7,29]],"date-time":"2010-07-29T04:50:35Z","timestamp":1280379035000},"page":"188-202","source":"Crossref","is-referenced-by-count":41,"title":["On Fixed-Parameter Tractable Parameterizations of SAT"],"prefix":"10.1007","author":[{"given":"Stefan","family":"Szeider","sequence":"first","affiliation":[]}],"member":"297","reference":[{"key":"15_CR1","doi-asserted-by":"publisher","first-page":"196","DOI":"10.1016\/0097-3165(86)90060-9","volume":"43","author":"R. Aharoni","year":"1986","unstructured":"Aharoni, R., Linial, N.: Minimal non-two-colorable hypergraphs and minimal unsatisfiable formulas. J. Combin. Theory Ser. A\u00a043, 196\u2013204 (1986)","journal-title":"J. Combin. Theory Ser. A"},{"key":"15_CR2","doi-asserted-by":"crossref","unstructured":"Alekhnovich, M., Razborov, A.A.: Satisfiability, branch-width and Tseitin tautologies. In: 43rd Annual IEEE Symposium on Foundations of Computer Science (FOCS 2002), pp. 593\u2013603 (2002)","DOI":"10.1109\/SFCS.2002.1181983"},{"issue":"2","key":"15_CR3","doi-asserted-by":"publisher","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 k-tree. SIAM J. Algebraic Discrete Methods\u00a08(2), 277\u2013284 (1987)","journal-title":"SIAM J. Algebraic Discrete Methods"},{"key":"15_CR4","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 (2003) (to appear)","DOI":"10.1109\/SFCS.2003.1238208"},{"issue":"6","key":"15_CR5","doi-asserted-by":"publisher","first-page":"1305","DOI":"10.1137\/S0097539793251219","volume":"25","author":"H.L. Bodlaender","year":"1996","unstructured":"Bodlaender, H.L.: A linear-time algorithm for finding tree-decompositions of small treewidth. SIAM J. Comput.\u00a025(6), 1305\u20131317 (1996)","journal-title":"SIAM J. Comput."},{"issue":"1-2","key":"15_CR6","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":"15_CR7","unstructured":"Cesati, M.: Compendium of parameterized problems (2001), \n                  \n                    http:\/\/bravo.ce.uniroma2.it\/home\/cesati\/research\/"},{"key":"15_CR8","unstructured":"Cook, S.A.: An exponential example for analytic tableaux (1972) (manuscript)"},{"issue":"1-2","key":"15_CR9","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. Discr. Appl. Math.\u00a0108(1-2), 23\u201352 (2001)","journal-title":"Discr. Appl. Math."},{"issue":"1-3","key":"15_CR10","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."},{"key":"15_CR11","doi-asserted-by":"publisher","first-page":"394","DOI":"10.1145\/368273.368557","volume":"5","author":"M. Davis","year":"1962","unstructured":"Davis, M., Logemann, G., Loveland, D.: A machine program for theoremproving. Comm. ACM\u00a05, 394\u2013397 (1962)","journal-title":"Comm. ACM"},{"key":"15_CR12","doi-asserted-by":"crossref","DOI":"10.1007\/978-1-4612-0515-9","volume-title":"Parameterized Complexity","author":"R.G. Downey","year":"1999","unstructured":"Downey, R.G., Fellows, M.R.: Parameterized Complexity. Springer, Heidelberg (1999)"},{"key":"15_CR13","unstructured":"Fleischner, H., F\u00f6ldes, S., Szeider, S.: Remarks on the concept of robust algorithm. Technical Report RRR 26-2001, Rutgers Center for Operations Research (RUTCOR) (April 2001)"},{"issue":"1","key":"15_CR14","doi-asserted-by":"publisher","first-page":"503","DOI":"10.1016\/S0304-3975(01)00337-1","volume":"289","author":"H. Fleischner","year":"2002","unstructured":"Fleischner, H., Kullmann, O., Szeider, S.: Polynomial-time recognition of minimal unsatisfiable formulas with fixed clause-variable difference. Theoret. Comput. Sci.\u00a0289(1), 503\u2013516 (2002)","journal-title":"Theoret. Comput. Sci."},{"key":"15_CR15","doi-asserted-by":"publisher","first-page":"89","DOI":"10.1016\/S0166-218X(99)00038-4","volume":"97","author":"J. Franco","year":"1999","unstructured":"Franco, J., Goldsmith, J., Schlipf, J., Speckenmeyer, E., Swaminathan, R.P.: An algorithm for the class of pure implicational formulas. Discr. Appl. Math.\u00a097, 89\u2013106 (1999)","journal-title":"Discr. Appl. Math."},{"key":"15_CR16","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"423","DOI":"10.1007\/3-540-46784-X_14","volume-title":"Graph-Theoretic Concepts in Computer Science","author":"M.C. Golumbic","year":"1999","unstructured":"Golumbic, M.C., Rotics, U.: On the clique-width of some perfect graph classes. In: Widmayer, P., Neyer, G., Eidenbenz, S. (eds.) WG 1999. LNCS, vol.\u00a01665, pp. 423\u2013443. Springer, Heidelberg (1999)"},{"key":"15_CR17","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"708","DOI":"10.1007\/3-540-48224-5_58","volume-title":"Automata, Languages and Programming","author":"G. Gottlob","year":"2001","unstructured":"Gottlob, G., Pichler, R.: Hypergraphs in model checking: Acyclicity and hypertree-width versus clique-width. In: Orejas, F., Spirakis, P.G., van Leeuwen, J. (eds.) ICALP 2001. LNCS, vol.\u00a02076, pp. 708\u2013719. Springer, Heidelberg (2001)"},{"issue":"1-2","key":"15_CR18","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-2), 55\u201386 (2002)","journal-title":"Artificial Intelligence"},{"key":"15_CR19","doi-asserted-by":"publisher","first-page":"127","DOI":"10.1016\/S0166-218X(99)00036-0","volume":"97","author":"P. Heusch","year":"1999","unstructured":"Heusch, P.: The complexity of the falsifiability problem for pure implicational formulas. Discr. Appl. Math.\u00a096\/97, 127\u2013138 (1999)","journal-title":"Discr. Appl. Math."},{"key":"15_CR20","unstructured":"Heusch, P., Porschen, S., Speckenmeyer, E.: Improving a fixed parameter tractability time bound for the shadow problem. Technical Report 2001-425, Universit\u00e4t zu K\u00f6ln (2001)"},{"key":"15_CR21","unstructured":"Kullmann, O.: Investigating a general hierarchy of polynomially decidable classes of CNF\u2019s based on short tree-like resolution proofs. Technical Report TR99\u2013041, Electronic Colloquium on Computational Complexity, ECCC (1999)"},{"key":"15_CR22","doi-asserted-by":"crossref","unstructured":"Kullmann, O.: An application of matroid theory to the SAT problem. In: Fifteenth Annual IEEE Conference on Computational Complexity, pp. 116\u2013124 (2000)","DOI":"10.1109\/CCC.2000.856741"},{"issue":"3-4","key":"15_CR23","doi-asserted-by":"publisher","first-page":"339","DOI":"10.1007\/BF02127974","volume":"17","author":"D. Pretolani","year":"1996","unstructured":"Pretolani, D.: Hierarchies of polynomially solvable satisfiability problems. Ann. Math. Artif. Intell.\u00a017(3-4), 339\u2013357 (1996)","journal-title":"Ann. Math. Artif. Intell."},{"issue":"3","key":"15_CR24","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 treewidth. J. Algorithms\u00a07(3), 309\u2013322 (1986)","journal-title":"J. Algorithms"},{"issue":"2","key":"15_CR25","doi-asserted-by":"publisher","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 treedecomposition. J. Combin. Theory Ser. B\u00a052(2), 153\u2013190 (1991)","journal-title":"J. Combin. Theory Ser. B"},{"issue":"1","key":"15_CR26","doi-asserted-by":"publisher","first-page":"65","DOI":"10.1006\/jctb.1995.1006","volume":"63","author":"N. Robertson","year":"1995","unstructured":"Robertson, N., Seymour, P.D.: Graph minors, XIII. The disjoint paths problem. J. Combin. Theory Ser. B\u00a063(1), 65\u2013110 (1995)","journal-title":"J. Combin. Theory Ser. B"},{"key":"15_CR27","unstructured":"Spinrad, J.P.: Representations of graphs. Book manuscript, Vanderbilt University (1997)"},{"key":"15_CR28","unstructured":"Szeider, S.: Generalizations of matched CNF formulas. Ann. Math. Artif. Intell., Special issue with selected papers from the 5th Int. Symp. on the Theory and Applications of Satisfiability Testing, SAT 2002 (2002) (to appear)"},{"key":"15_CR29","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"548","DOI":"10.1007\/3-540-45071-8_55","volume-title":"Computing and Combinatorics","author":"S. Szeider","year":"2003","unstructured":"Szeider, S.: Minimal unsatisfiable formulas with bounded clause-variable difference are fixed-parameter tractable. In: Warnow, T.J., Zhu, B. (eds.) COCOON 2003. LNCS, vol.\u00a02697, pp. 548\u2013558. Springer, Heidelberg (2003)"},{"issue":"4","key":"15_CR30","doi-asserted-by":"publisher","first-page":"425","DOI":"10.2178\/bsl\/1203350879","volume":"1","author":"A. Urquhart","year":"1995","unstructured":"Urquhart, A.: The complexity of propositional proofs. Bull. of Symbolic Logic\u00a01(4), 425\u2013467 (1995)","journal-title":"Bull. of Symbolic Logic"},{"key":"15_CR31","first-page":"81","volume-title":"Very Large Data Bases, 7th International Conference","author":"M. Yannakakis","year":"1981","unstructured":"Yannakakis, M.: Algorithms for acyclic database schemes. In: Zaniolo, C., Delobel, C. (eds.) Very Large Data Bases, 7th International Conference, Cannes, France, September 9-11, pp. 81\u201394. IEEE Computer Society, Los Alamitos (1981)"}],"container-title":["Lecture Notes in Computer Science","Theory and Applications of Satisfiability Testing"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-540-24605-3_15","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,3,17]],"date-time":"2019-03-17T11:06:26Z","timestamp":1552820786000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-540-24605-3_15"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2004]]},"ISBN":["9783540208518","9783540246053"],"references-count":31,"URL":"https:\/\/doi.org\/10.1007\/978-3-540-24605-3_15","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2004]]}}}