Max Horn SAT and the minimum cut problem in directed hypergraphs

DOI10.1007/BF01581727zbMATH Open0894.90152OpenAlexW2069861393MaRDI QIDQ1380929FDOQ1380929

Authors: D. Pretolani, Giorgio Gallo, Claudio Gentile, Gabriella Rago 

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

Recommendations

• Directed hypergraphs and Horn minimization
• Maximum directed cuts in graphs with degree constraints
• Maximum directed cuts in acyclic digraphs
• Maximum directed cuts in digraphs with degree restriction
• Combinatorial approximation algorithms for the maximum directed cut problem
• Minimum cuts and sparsification in hypergraphs
• MaxCut in ${\bm H)$-Free Graphs
• Complexity of the max cut problem with the minimal domination constraint
• Hardness of cut problems in directed graphs

zbMATH Keywords

minimum cutdisjunctive programmingmaximum satisfiabilityHorn clausesdirected 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)

Cites Work

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

Cited In (6)

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

Uses Software

• DIMACS

This page was built for publication: Max Horn SAT and the minimum cut problem in directed hypergraphs

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1380929)