{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,11,26]],"date-time":"2025-11-26T04:45:22Z","timestamp":1764132322858},"reference-count":18,"publisher":"Springer Science and Business Media LLC","issue":"1-4","license":[{"start":{"date-parts":[[2004,12,31]],"date-time":"2004-12-31T00:00:00Z","timestamp":1104451200000},"content-version":"tdm","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Ann Math Artif Intell"],"published-print":{"date-parts":[[2005,1]]},"DOI":"10.1007\/s10472-005-0432-6","type":"journal-article","created":{"date-parts":[[2005,3,2]],"date-time":"2005-03-02T19:19:42Z","timestamp":1109791182000},"page":"223-238","source":"Crossref","is-referenced-by-count":11,"title":["Generalizations of matched CNF formulas"],"prefix":"10.1007","volume":"43","author":[{"given":"Stefan","family":"Szeider","sequence":"first","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2004,12,31]]},"reference":[{"key":"432_CR1","doi-asserted-by":"crossref","first-page":"196","DOI":"10.1016\/0097-3165(86)90060-9","volume":"43","author":"R. Aharoni","year":"1986","unstructured":"R. Aharoni and N. Linial, Minimal non-two-colorable hypergraphs and minimal unsatisfiable formulas, J. Combin. Theory Ser. A 43 (1986) 196\u2013204.","journal-title":"J. Combin. Theory Ser. A"},{"key":"432_CR2","volume-title":"Graph Theory","author":"R. Diestel","year":"2000","unstructured":"R. Diestel, Graph Theory, 2nd ed., Graduate Texts in Mathematics, Vol. 173 (Springer, New York, 2000).","edition":"2nd ed."},{"key":"432_CR3","doi-asserted-by":"crossref","unstructured":"R.G. Downey and M.R. Fellows, Parameterized Complexity (Springer, 1999).","DOI":"10.1007\/978-1-4612-0515-9"},{"issue":"1","key":"432_CR4","doi-asserted-by":"crossref","first-page":"59","DOI":"10.1080\/00207160008805009","volume":"76","author":"T. Eiter","year":"2000","unstructured":"T. Eiter and G. Gottlob, Complexity results for some eigenvector problems, International Journal of Computer Mathematics 76(1) (2000) 59\u201374.","journal-title":"International Journal of Computer Mathematics"},{"issue":"1","key":"432_CR5","doi-asserted-by":"crossref","first-page":"503","DOI":"10.1016\/S0304-3975(01)00337-1","volume":"289","author":"H. Fleischner","year":"2002","unstructured":"H. Fleischner, O. Kullmann and S. Szeider, Polynomial-time recognition of minimal unsatisfiable formulas with fixed clause-variable difference, Theoretical Computer Science 289(1) (2002) 503\u2013516.","journal-title":"Theoretical Computer Science"},{"key":"432_CR6","doi-asserted-by":"crossref","first-page":"177","DOI":"10.1016\/S0166-218X(01)00358-4","volume":"125","author":"J. Franco","year":"2003","unstructured":"J. Franco and A. Van Gelder, A perspective on certain polynomial time solvable classes of satisfiability, Discrete Applied Mathematics 125 (2003) 177\u2013214.","journal-title":"Discrete Applied Mathematics"},{"key":"432_CR7","volume-title":"Computers and Intractability","author":"M.R. Garey","year":"1979","unstructured":"M.R. Garey and D.R. Johnson, Computers and Intractability (Freeman, New York, 1979)."},{"key":"432_CR8","doi-asserted-by":"crossref","unstructured":"P. Hell, Graph packings, in: Proceedings for the 6th International Conference on Graph Theory, ed. I. Rusu, Electronic Notes in Discrete Mathematics, Vol. 5 (2000).","DOI":"10.1016\/S1571-0653(05)80154-4"},{"key":"432_CR9","volume-title":"Propositional Logic: Deduction and Algorithms","author":"H. Kleine B\u00fcning","year":"1999","unstructured":"H. Kleine B\u00fcning and T. Lettman, Propositional Logic: Deduction and Algorithms (Cambridge Univ. Press, Cambridge, 1999)."},{"key":"432_CR10","doi-asserted-by":"crossref","unstructured":"H. Kleine B\u00fcning and X. Zhao, Satisfiable formulas closed under replacement, in: Proceedings for the Workshop on Theory and Applications of Satisfiability, eds. H. Kautz and B. Selman, Electronic Notes in Discrete Mathematics, Vol. 9 (2001).","DOI":"10.1016\/S1571-0653(04)00313-0"},{"issue":"1\u20133","key":"432_CR11","doi-asserted-by":"crossref","first-page":"99","DOI":"10.1016\/S0166-218X(00)00262-6","volume":"107","author":"O. Kullmann","year":"2000","unstructured":"O. Kullmann, Investigations on autark assignments, Discrete Applied Mathematics 107(1\u20133) (2000) 99\u2013137.","journal-title":"Discrete Applied Mathematics"},{"issue":"2","key":"432_CR12","doi-asserted-by":"crossref","first-page":"209","DOI":"10.1016\/S0166-218X(02)00406-7","volume":"130","author":"O. Kullmann","year":"2003","unstructured":"O. Kullmann, Lean clause-sets: Generalizations of minimally unsatisfiable clause-sets, Discrete Applied Mathematics 130(2) (2003) 209\u2013249.","journal-title":"Discrete Applied Mathematics"},{"key":"432_CR13","volume-title":"Matching Theory","author":"L. Lov\u00e1sz","year":"1986","unstructured":"L. Lov\u00e1sz and M.D. Plummer, Matching Theory, Annals of Discrete Mathematics, Vol. 29 (North-Holland, Amsterdam, 1986)."},{"key":"432_CR14","unstructured":"C.H. Papadimitriou, Computational Complexity (Addison-Wesley, 1994)."},{"key":"432_CR15","unstructured":"M. Schaefer, Completeness in the polynomial-time hierarchy, Technical Report TR01-009, School of CTI, DePaul University, Chicago, IL (2001)."},{"issue":"1","key":"432_CR16","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1016\/0304-3975(76)90061-X","volume":"3","author":"L.J. Stockmeyer","year":"1976","unstructured":"L.J. Stockmeyer, The polynomial-time hierarchy, Theoretical Computer Science 3(1) (1976) 1\u201322.","journal-title":"Theoretical Computer Science"},{"key":"432_CR17","doi-asserted-by":"crossref","unstructured":"S. Szeider, Minimal unsatisfiable formulas with bounded clause-variable difference are fixed-parameter tractable, in: Proceedings of the 9th International Computing and Combinatorics Conference (COCOON\u201903), eds. T. Warnow and B. Zhu, Lecture Notes in Computer Science, Vol. 2697 (2003) pp. 548\u2013558.","DOI":"10.1007\/3-540-45071-8_55"},{"issue":"1","key":"432_CR18","doi-asserted-by":"crossref","first-page":"85","DOI":"10.1016\/0166-218X(84)90081-7","volume":"8","author":"C.A. Tovey","year":"1984","unstructured":"C.A. Tovey, A simplified NP-complete satisfiability problem, Discrete Applied Mathematics 8(1) (1984) 85\u201389.","journal-title":"Discrete Applied Mathematics"}],"container-title":["Annals of Mathematics and Artificial Intelligence"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s10472-005-0432-6.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/article\/10.1007\/s10472-005-0432-6\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s10472-005-0432-6","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,5,29]],"date-time":"2019-05-29T17:51:48Z","timestamp":1559152308000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/s10472-005-0432-6"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2004,12,31]]},"references-count":18,"journal-issue":{"issue":"1-4","published-print":{"date-parts":[[2005,1]]}},"alternative-id":["432"],"URL":"https:\/\/doi.org\/10.1007\/s10472-005-0432-6","relation":{},"ISSN":["1012-2443","1573-7470"],"issn-type":[{"value":"1012-2443","type":"print"},{"value":"1573-7470","type":"electronic"}],"subject":[],"published":{"date-parts":[[2004,12,31]]}}}