{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,2,14]],"date-time":"2026-02-14T02:32:56Z","timestamp":1771036376660,"version":"3.50.1"},"reference-count":18,"publisher":"Springer Science and Business Media LLC","issue":"2","license":[{"start":{"date-parts":[[1998,1,1]],"date-time":"1998-01-01T00:00:00Z","timestamp":883612800000},"content-version":"tdm","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Mathematical Programming"],"published-print":{"date-parts":[[1998,1]]},"DOI":"10.1007\/bf01581727","type":"journal-article","created":{"date-parts":[[2005,4,28]],"date-time":"2005-04-28T09:39:14Z","timestamp":1114681154000},"page":"213-237","source":"Crossref","is-referenced-by-count":9,"title":["Max Horn SAT and the minimum cut problem in directed hypergraphs"],"prefix":"10.1007","volume":"80","author":[{"given":"G.","family":"Gallo","sequence":"first","affiliation":[]},{"given":"C.","family":"Gentile","sequence":"additional","affiliation":[]},{"given":"D.","family":"Pretolani","sequence":"additional","affiliation":[]},{"given":"G.","family":"Rago","sequence":"additional","affiliation":[]}],"member":"297","reference":[{"key":"CR1","doi-asserted-by":"crossref","first-page":"177","DOI":"10.1016\/0166-218X(93)90045-P","volume":"42","author":"G. Gallo","year":"1993","unstructured":"G. Gallo, G. Longo, S. Nguyen, S. Pallottino, Directed Hypergraphs and Applications, Discrete Applied Mathematics 42 (1993) 177\u2013201.","journal-title":"Discrete Applied Mathematics"},{"key":"CR2","volume-title":"Satisfiability and Hypergraphs","author":"D. Pretolani","year":"1993","unstructured":"D. Pretolani, Satisfiability and Hypergraphs, Ph.D. Thesis, TD-12\/93, Dipartimento di Informatica, University of Pisa, Italy, 1993."},{"key":"CR3","unstructured":"G. Gallo, G. Rago, A Hypergraphs Approach to Logical Inference for Datalog Formulae, TR 28\/90, Dipartimento di Informatica, Universit\u00e0 di Pisa."},{"key":"CR4","volume-title":"Optimization, Hypergraphs and Logical Inference","author":"G. Rago","year":"1993","unstructured":"G. Rago, Optimization, Hypergraphs and Logical Inference, Ph.D. Thesis, TD-4\/94, Dipartimento di Informatica, University of Pisa, Italy, 1993."},{"key":"CR5","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1016\/0020-0190(87)90028-7","volume":"26","author":"B. Jaumard","year":"1987\/1988","unstructured":"B. Jaumard, B. Simeone, On the complexity of the maximum satisfiability problem for Horn formulas, Information Processing Letters 26 (1987\/1988) 1\u20134.","journal-title":"Information Processing Letters"},{"key":"CR6","doi-asserted-by":"crossref","first-page":"397","DOI":"10.1007\/BF01209713","volume":"30","author":"J. Kratochv\u00edl","year":"1993","unstructured":"J. Kratochv\u00edl, M. K\u0159iv\u00e1nek, Satisfiability of co-nested formulas, Acta Informatica 30 (1993) 397\u2013403.","journal-title":"Acta Informatica"},{"key":"CR7","doi-asserted-by":"crossref","first-page":"656","DOI":"10.1137\/S0895480192243516","volume":"7","author":"M.X. Goemans","year":"1994","unstructured":"M.X. Goemans, D.P. Williamson, New 3\/4-approximation algorithms for the maximum satisfiability problem, SIAM Journal on Discrete Mathematics 7 (1994) 656\u2013666.","journal-title":"SIAM Journal on Discrete Mathematics"},{"key":"CR8","doi-asserted-by":"crossref","first-page":"1115","DOI":"10.1145\/227683.227684","volume":"42","author":"M.X. Goemans","year":"1995","unstructured":"M.X. Goemans, D.P. Williamson, Improved approximation algorithms for maximum cut and satisfiability problems using semidefinite programming, J. ACM 42 (1995) 1115\u20131145.","journal-title":"J. ACM"},{"key":"CR9","doi-asserted-by":"crossref","unstructured":"J.M. Bourjolly, P.L. Hammer, W.R. Pulleyblank, B. Simeone, Boolean Combinatorial Bounding of Maximum 2-Satisfiability, RRR 5-92, RUTCOR, Rutgers University, 1992.","DOI":"10.1016\/B978-0-08-040806-4.50007-1"},{"key":"CR10","doi-asserted-by":"crossref","unstructured":"J. Cheriyan, W.H. Cunningham, L. Tuncel, Y. Wang, A Linear Programming and Rounding Approach to Max 2-SAT, in: D.S. Johnson, M.A. Trick (Eds.),Cliques, Coloring, and Satisfiability: Second DIMACS Implementation Challenge, DIMACS Series in Discrete Mathematics and Theoretical Computer Science 26, American Mathematical Society (1996).","DOI":"10.1090\/dimacs\/026\/19"},{"key":"CR11","doi-asserted-by":"crossref","first-page":"195","DOI":"10.1007\/BF02614364","volume":"78","author":"G. Gallo","year":"1997","unstructured":"G. Gallo, R. Cambini, M.G. Scutell\u00e0, Flows on hypergraphs, Mathematical Programming 78 (1997) 195\u2013217.","journal-title":"Mathematical Programming"},{"key":"CR12","doi-asserted-by":"crossref","first-page":"267","DOI":"10.1016\/0743-1066(84)90014-1","volume":"1","author":"W.F. Dowling","year":"1984","unstructured":"W.F. Dowling, J.H. Gallier, Linear-time algorithms for testing the satisfiability of propositional Horn formulae, Journal of Logic Programming 1 (1984) 267\u2013284.","journal-title":"Journal of Logic Programming"},{"key":"CR13","doi-asserted-by":"crossref","first-page":"97","DOI":"10.1016\/0304-3975(90)90030-L","volume":"72","author":"G. Ausiello","year":"1990","unstructured":"G. Ausiello, G.F. Italiano, U. Nanni, Dynamic maintenance of directed hypergraphs, Theoretical Computer Science 72 (1990) 97\u2013117.","journal-title":"Theoretical Computer Science"},{"issue":"3","key":"CR14","doi-asserted-by":"crossref","first-page":"375","DOI":"10.1007\/BF01581090","volume":"57","author":"R.G. Jeroslow","year":"1992","unstructured":"R.G. Jeroslow, K. Martin, R.L. Rardin, J. Wang, Gainfree Leontief substitution flow problems, Mathematical Programming 57 (3) (1992) 375\u2013414.","journal-title":"Mathematical Programming"},{"key":"CR15","unstructured":"R.G. Jeroslow, Logic-based decision support \u2014 mixed integer model formulation, Annals of Discrete Mathematics 40 (1989)."},{"key":"CR16","doi-asserted-by":"crossref","first-page":"7","DOI":"10.1287\/ijoc.1.1.7","volume":"1","author":"R.G. Jeroslow","year":"1989","unstructured":"R.G. Jeroslow, J. Wang, Dynamic programming, integral polyhedra and Horn clause knowledge base, ORSA Journal on Computing 1 (1989) 7\u201319.","journal-title":"ORSA Journal on Computing"},{"key":"CR17","doi-asserted-by":"crossref","DOI":"10.1002\/9781118627372","volume-title":"Integer and Combinatorial Optimization","author":"G.L. Nemhauser","year":"1988","unstructured":"G.L. Nemhauser, L.A. Wolsey, Integer and Combinatorial Optimization, Wiley, UK, 1988."},{"key":"CR18","unstructured":"J.N. Hooker, V. Vinay, An empirical study of branching rules for satisfiability, presented at the third Symposium on Artificial Intelligence and Mathematics, January 1994."}],"container-title":["Mathematical Programming"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/BF01581727.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/article\/10.1007\/BF01581727\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/BF01581727","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2024,1,25]],"date-time":"2024-01-25T08:42:42Z","timestamp":1706172162000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/BF01581727"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[1998,1]]},"references-count":18,"journal-issue":{"issue":"2","published-print":{"date-parts":[[1998,1]]}},"alternative-id":["BF01581727"],"URL":"https:\/\/doi.org\/10.1007\/bf01581727","relation":{},"ISSN":["0025-5610","1436-4646"],"issn-type":[{"value":"0025-5610","type":"print"},{"value":"1436-4646","type":"electronic"}],"subject":[],"published":{"date-parts":[[1998,1]]}}}