Uniquely solvable quadratic Boolean equations

DOI10.1016/0166-218X(85)90068-XzbMath0584.06008MaRDI QIDQ1070255

Pierre Hansen, Brigitte Jaumard

Publication date: 1985

Published in: Discrete Applied Mathematics (Search for Journal in Brave)

zbMATH Keywords

unique solutionimplication graphlinear- time algorithmquadratic Boolean equation

Mathematics Subject Classification ID

Boolean programming (90C09) Boolean algebras (Boolean rings) (06E99) Graph theory (05C99) Structure theory of Boolean algebras (06E05)

Related Items

2-satisfiability and diagnosing fault processors in massively parallel computing systems, The unique Horn-satisfiability problem and quadratic Boolean equations., A linear expected-time algorithm for deriving all logical conclusions implied by a set of boolean inequalities, A decomposition method for minimizing quadratic pseudo-Boolean functions, On quadratic Boolean equations, On 2-QBF truth testing in parallel, Unique Horn renaming and Unique 2-Satisfiability, Counting the number of solutions for instances of satisfiability, A linear time algorithm for unique Horn satisfiability

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Linear Boolean equations and generalized minterms
• Linear equations and interpolation in Boolean algebra
• A switching algorithm for the solution of quadratic Boolean equations
• A cascade algorithm for the logical closure of a set of binary relations
• Testing for Equality between Maximum Matching and Minimum Node Covering
• A linear-time algorithm for testing the truth of certain quantified Boolean formulas
• On the unique satisfiability problem
• Degree-two Inequalities, Clique Facets, and Biperfect Graphs
• Logical Reduction Methods in Zero-One Programming—Minimal Preferred Variables
• On the Complexity of Timetable and Multicommodity Flow Problems
• Note on the Condition that a Boolean Equation Have a Unique Solution
• Depth-First Search and Linear Graph Algorithms