A linear expected-time algorithm for deriving all logical conclusions implied by a set of boolean inequalities

Hansen, Pierre; Jaumard, Brigitte; Minoux, Michel

Hansen, Pierre; Jaumard, Brigitte; Minoux, Michel (1986), A linear expected-time algorithm for deriving all logical conclusions implied by a set of boolean inequalities, Mathematical Programming, 34, 2, p. 223-231. http://dx.doi.org/10.1007/BF01580586

Type

Article accepté pour publication ou publié

Date

1986

Journal name

Mathematical Programming

Volume

Number

Publisher

Springer

Pages

223-231

Abstract (EN)

Consider a set R of m binary relations on a set of n boolean variables. R may imply a contradiction, the fixation of some variables at 0 or at 1 and/or the identification of some pairs of variables in direct or complemented form. An O(n) expected-time algorithm is given for the derivation of all such logical conclusions. Computational experiments with problems involving up to 2000 variables are reported on. The proposed algorithm is more than 100 times faster than previous methods when n ≥ 100.

Subjects / Keywords

Boolean Inequalities; Implication Graph; Depth-First Search; Strongly Connected Components; Transitive Closure; 0–1 Programming