Max Horn SAT and the minimum cut problem in directed hypergraphs

DOI10.1007/BF01581727zbMath0894.90152OpenAlexW2069861393MaRDI QIDQ1380929

Daniele Pretolani, Gabriella Rago, Claudio Gentile, Giorgio Gallo

Publication date: 11 March 1998

Published in: Mathematical Programming. Series A. Series B (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/bf01581727

zbMATH Keywords

minimum cutHorn clausesdisjunctive programmingmaximum satisfiabilitydirected hypergraphgeneralized set coveringmaximum Horn satisfiability problemminimum cardinality cut

Mathematics Subject Classification ID

Programming involving graphs or networks (90C35) Deterministic network models in operations research (90B10)

Related Items

Good and nice colorings of balanced hypergraphs ⋮ Hypernetworks in a directed hypergraph ⋮ On the complexity of strongly connected components in directed hypergraphs ⋮ Finding the \(K\) shortest hyperpaths ⋮ Partially dynamic maintenance of minimum weight hyperpaths

Uses Software

• DIMACS

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Dynamic maintenance of directed hypergraphs
• On the complexity of the maximum satisfiability problem for Horn formulas
• Logic-based decision support. Mixed integer model formulation
• Satisfiability of co-nested formulas
• Flows on hypergraphs
• Gainfree Leontief substitution flow problems
• Directed hypergraphs and applications
• Linear-time algorithms for testing the satisfiability of propositional horn formulae
• Dynamic Programming, Integral Polyhedra and Horn Clause Knowledge Base
• New $\frac{3}{4}$-Approximation Algorithms for the Maximum Satisfiability Problem
• Improved approximation algorithms for maximum cut and satisfiability problems using semidefinite programming