{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,4,25]],"date-time":"2026-04-25T14:03:27Z","timestamp":1777125807910,"version":"3.51.4"},"reference-count":19,"publisher":"Elsevier BV","issue":"1","license":[{"start":{"date-parts":[[2002,10,1]],"date-time":"2002-10-01T00:00:00Z","timestamp":1033430400000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/www.elsevier.com\/tdm\/userlicense\/1.0\/"},{"start":{"date-parts":[[2013,7,17]],"date-time":"2013-07-17T00:00:00Z","timestamp":1374019200000},"content-version":"vor","delay-in-days":3942,"URL":"https:\/\/www.elsevier.com\/open-access\/userlicense\/1.0\/"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Theoretical Computer Science"],"published-print":{"date-parts":[[2002,10]]},"DOI":"10.1016\/s0304-3975(01)00337-1","type":"journal-article","created":{"date-parts":[[2002,10,7]],"date-time":"2002-10-07T16:25:18Z","timestamp":1034007918000},"page":"503-516","source":"Crossref","is-referenced-by-count":62,"title":["Polynomial-time recognition of minimal unsatisfiable formulas with fixed clause-variable difference"],"prefix":"10.1016","volume":"289","author":[{"given":"Herbert","family":"Fleischner","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Oliver","family":"Kullmann","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Stefan","family":"Szeider","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"78","reference":[{"key":"10.1016\/S0304-3975(01)00337-1_BIB1","doi-asserted-by":"crossref","first-page":"196","DOI":"10.1016\/0097-3165(86)90060-9","article-title":"Minimal non-two-colorable hypergraphs and minimal unsatisfiable formulas","volume":"43","author":"Aharoni","year":"1986","journal-title":"J. Combin. Theory Ser. A"},{"issue":"4","key":"10.1016\/S0304-3975(01)00337-1_BIB2","doi-asserted-by":"crossref","first-page":"237","DOI":"10.1016\/0020-0190(91)90195-N","article-title":"Computing a maximum cardinality matching in a bipartite graph in time O(n1.5m\/logn)","volume":"37","author":"Alt","year":"1991","journal-title":"Inform. Process. Lett."},{"key":"10.1016\/S0304-3975(01)00337-1_BIB3","doi-asserted-by":"crossref","first-page":"844","DOI":"10.1073\/pnas.43.9.842","article-title":"Two theorems in graph theory","volume":"43","author":"Berge","year":"1957","journal-title":"Proc. Nat. Acad. Sci. USA"},{"key":"10.1016\/S0304-3975(01)00337-1_BIB4","doi-asserted-by":"crossref","first-page":"229","DOI":"10.1023\/A:1018924526592","article-title":"An efficient algorithm for the minimal unsatisfiability problem for a subclass of CNF","volume":"23","author":"Davidov","year":"1998","journal-title":"Ann. Math. Artif. Intell."},{"key":"10.1016\/S0304-3975(01)00337-1_BIB5","series-title":"Graph theory, Graduate Texts in Mathematics, Vol. 173","author":"Diestel","year":"2000"},{"key":"10.1016\/S0304-3975(01)00337-1_BIB6","unstructured":"H. Fleischner, S. Szeider, Polynomial-time recognition of minimal unsatisfiable formulas with fixed clause-variable difference, Technical Report TR00-049, Electronic Colloquium on Computational Complexity (ECCC), 2000."},{"key":"10.1016\/S0304-3975(01)00337-1_BIB7","doi-asserted-by":"crossref","unstructured":"J. Franco, A. Van Gelder, A perspective on certain polynomial time solvable classes of satisfiability, Discr. Appl. Math., to appear.","DOI":"10.1016\/S0166-218X(01)00358-4"},{"key":"10.1016\/S0304-3975(01)00337-1_BIB8","doi-asserted-by":"crossref","unstructured":"Z. Galil, Efficient algorithms for finding maximal matching in graphs, in: CAAP \u201983 (L'Aquila, 1983), Vol. 159, Springer, Berlin, 1983, pp. 90\u2013113.","DOI":"10.1007\/3-540-12727-5_4"},{"key":"10.1016\/S0304-3975(01)00337-1_BIB9","first-page":"225","article-title":"An n5\/2 algorithm for maximum matchings in bipartite graphs","volume":"2","author":"Hopcroft","year":"1973","journal-title":"J. Comput."},{"key":"10.1016\/S0304-3975(01)00337-1_BIB10","series-title":"Handbook of Theoretical Computer Science, Vol. A, Chap. 2","first-page":"67","article-title":"A catalog of complexity classes","author":"Johnson","year":"1990"},{"key":"10.1016\/S0304-3975(01)00337-1_BIB11","series-title":"CSL\u201998, LNCS, Vol. 1584","first-page":"171","article-title":"An upper bound for minimal resolution refutations","author":"Kleine B\u00fcning","year":"1999"},{"issue":"1\u20133","key":"10.1016\/S0304-3975(01)00337-1_BIB12","doi-asserted-by":"crossref","first-page":"83","DOI":"10.1016\/S0166-218X(00)00245-6","article-title":"On subclasses of minimal unsatisfiable formulas","volume":"107","author":"Kleine B\u00fcning","year":"2000","journal-title":"Discr. Appl. Math."},{"key":"10.1016\/S0304-3975(01)00337-1_BIB13","doi-asserted-by":"crossref","unstructured":"O. Kullmann, An application of matroid theory to the SAT problem, in: Fifteenth Ann. IEEE Conf. of Computational Complexity, 2000, pp. 116\u2013124, see also TR00-018, Electronic Colloquium on Computational Complexity (ECCC), March, 2000.","DOI":"10.1109\/CCC.2000.856741"},{"issue":"1\u20133","key":"10.1016\/S0304-3975(01)00337-1_BIB14","doi-asserted-by":"crossref","first-page":"99","DOI":"10.1016\/S0166-218X(00)00262-6","article-title":"Investigations on autark assignments","volume":"107","author":"Kullmann","year":"2000","journal-title":"Discr. Appl. Math."},{"key":"10.1016\/S0304-3975(01)00337-1_BIB15","doi-asserted-by":"crossref","unstructured":"O. Kullmann, Lean clause-sets: generalizations of minimally unsatisfiable clause-sets, Discr. Appl. Math., to appear.","DOI":"10.1016\/S0166-218X(02)00406-7"},{"key":"10.1016\/S0304-3975(01)00337-1_BIB16","series-title":"mATCHING THEORY, aNNALS OF dISCRETE mATHEMATICS, Vol. 29","author":"lOV\u00c1SZ","year":"1986"},{"key":"10.1016\/S0304-3975(01)00337-1_BIB17","doi-asserted-by":"crossref","first-page":"341","DOI":"10.1093\/comjnl\/8.4.341","article-title":"Theorem-proving for computers: some results on resolution and renaming","volume":"8","author":"Meltzer","year":"1966","journal-title":"Comp. J."},{"issue":"1","key":"10.1016\/S0304-3975(01)00337-1_BIB18","doi-asserted-by":"crossref","first-page":"2","DOI":"10.1016\/0022-0000(88)90042-6","article-title":"The complexity of facets resolved","volume":"37","author":"Papadimitriou","year":"1988","journal-title":"J. Comput. System Sci."},{"issue":"7","key":"10.1016\/S0304-3975(01)00337-1_BIB19","doi-asserted-by":"crossref","first-page":"720","DOI":"10.1007\/BF02878991","article-title":"Two tractable subclasses of minimal unsatisfiable formulas","volume":"42","author":"Zhao","year":"1999","journal-title":"Sci. China Ser. A"}],"container-title":["Theoretical Computer Science"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/api.elsevier.com\/content\/article\/PII:S0304397501003371?httpAccept=text\/xml","content-type":"text\/xml","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/api.elsevier.com\/content\/article\/PII:S0304397501003371?httpAccept=text\/plain","content-type":"text\/plain","content-version":"vor","intended-application":"text-mining"}],"deposited":{"date-parts":[[2019,4,8]],"date-time":"2019-04-08T21:22:29Z","timestamp":1554758549000},"score":1,"resource":{"primary":{"URL":"https:\/\/linkinghub.elsevier.com\/retrieve\/pii\/S0304397501003371"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2002,10]]},"references-count":19,"journal-issue":{"issue":"1","published-print":{"date-parts":[[2002,10]]}},"alternative-id":["S0304397501003371"],"URL":"https:\/\/doi.org\/10.1016\/s0304-3975(01)00337-1","relation":{},"ISSN":["0304-3975"],"issn-type":[{"value":"0304-3975","type":"print"}],"subject":[],"published":{"date-parts":[[2002,10]]}}}