A linear expected-time algorithm for deriving all logical conclusions implied by a set of boolean inequalities
From MaRDI portal
Publication:3730348
DOI10.1007/BF01580586zbMath0596.90067MaRDI QIDQ3730348
Pierre Hansen, Brigitte Jaumard, Michel Minoux
Publication date: 1986
Published in: Mathematical Programming (Search for Journal in Brave)
transitive closuredepth-first searchprogrammingbinary relationsBoolean variablesstrongly connected componentsimplication graph0-1Boolean inequalitieslogical conclusion
Related Items
Polynomial-time inference of all valid implications for Horn and related formulae, Binary integer programs with two variables per inequality, A decomposition method for minimizing quadratic pseudo-Boolean functions, Logical and inequality implications for reducing the size and difficulty of quadratic unconstrained binary optimization problems, Modeling and integer programming techniques applied to propositional calculus, An analytical approach to global optimization, Minimum sum of diameters clustering, A threshold for unsatisfiability, Algorithms for the maximum satisfiability problem, Computational experience with an interior point algorithm on the satisfiability problem, On the r,s-SAT satisfiability problem and a conjecture of Tovey
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Uniquely solvable quadratic Boolean equations
- An efficient algorithm for the transitive closure and a linear worst-case complexity result for a class of sparse graphs
- A cascade algorithm for the logical closure of a set of binary relations
- A linear-time algorithm for testing the truth of certain quantified Boolean formulas
- Gaussian elimination is not optimal
- Efficient determination of the transitive closure of a directed graph
- Degree-two Inequalities, Clique Facets, and Biperfect Graphs
- Solving Large-Scale Zero-One Linear Programming Problems
- Logical Reduction Methods in Zero-One Programming—Minimal Preferred Variables
- Linear expected-time algorithms for connectivity problems
- On the Asymptotic Complexity of Matrix Multiplication
- A transitive closure algorithm
- Depth-First Search and Linear Graph Algorithms
- A Theorem on Boolean Matrices
