ISSN:
1436-4646
Keywords:
Boolean Inequalities
;
Implication Graph
;
Depth-First Search
;
Strongly Connected Components
;
Transitive Closure
;
0–1 Programming
Source:
Springer Online Journal Archives 1860-2000
Topics:
Computer Science
,
Mathematics
Notes:
Abstract Consider a setR ofm binary relations on a set ofn 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 whenn ≥ 100.
Type of Medium:
Electronic Resource
URL:
http://dx.doi.org/10.1007/BF01580586
Permalink