A linear time algorithm for unique Horn satisfiability
From MaRDI portal
Recommendations
- Unique satisfiability of Horn sets can be solved in nearly linear time
- Unique Horn renaming and Unique 2-Satisfiability
- The unique Horn-satisfiability problem and quadratic Boolean equations.
- Linear-time algorithms for testing the satisfiability of propositional horn formulae
- On the complexity of unique circuit SAT
Cites work
- A linear-time algorithm for a special case of disjoint set union
- A new algorithm for the propositional satisfiability problem
- Depth-First Search and Linear Graph Algorithms
- Directed hypergraphs and applications
- Linear-time algorithms for testing the satisfiability of propositional horn formulae
- On the unique satisfiability problem
- Polynomial-time inference of all valid implications for Horn and related formulae
- The unique Horn-satisfiability problem and quadratic Boolean equations.
- Unique satisfiability of Horn sets can be solved in nearly linear time
- Uniquely solvable quadratic Boolean equations
Cited in
(7)- Partially dynamic maintenance of minimum weight hyperpaths
- Complexity of pairwise shortest path routing in the grid
- Unique satisfiability of Horn sets can be solved in nearly linear time
- A linear algorithm for renaming a set of clauses as a Horn set
- scientific article; zbMATH DE number 991069 (Why is no real title available?)
- About some UP-based polynomial fragments of SAT
- Unique Horn renaming and Unique 2-Satisfiability
This page was built for publication: A linear time algorithm for unique Horn satisfiability
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1313762)
