×

A linear expected-time algorithm for deriving all logical conclusions implied by a set of Boolean inequalities. (English) Zbl 0596.90067

If R is a set of m binary relations on a set of n Boolean variables, then R may imply logical conclusion of the types: contradiction, fixation and identification. A way to derive all logical conclusions implied by R is to construct the logical closure \(\bar R\) of R and to scan all pairs of variables. The known algorithms for detecting all fixations require no less computations than to find \(\bar R\) of R, i.e. \(O(n^ 3)\). The algorithm proposed by the authors has a linear expected-time if the m relations of R are randomly chosen with a uniform probability among all binary relations. Computational experiments are also presented.
Reviewer: N.Y.Yanev

MSC:

90C09 Boolean programming
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] B. Aspvall, M.F. Plass and R.E. Tarjan, ”A linear-time algorithm for testing the truth of certain quantified boolean formulas”,Information Processing Letters 8 (1979) 121–123. · Zbl 0398.68042 · doi:10.1016/0020-0190(79)90002-4
[2] R. Breu and C.A. Burdet, ”Branch and bound experiments in zero–one programming”,Mathematical Programming Study 2 (1974) 1–50. · Zbl 0358.90038
[3] D. Coppersmith and S. Winograd, ”On the asymptotic complexity of matrix multiplication”,SIAM Journal on Computing 11 (1982) 472–492. · Zbl 0486.68030 · doi:10.1137/0211038
[4] H. Crowder, E.L. Johnson and M. Padberg, ”Solving large-scale zero–one linear programming problems”,Operations Research 31 (1983) 803–834. · Zbl 0576.90065 · doi:10.1287/opre.31.5.803
[5] M.J. Fisher and A.R. Meyer, ”Boolean matrix multiplication and transitive closure”,Proceedings 12th Annual Symposium on Switching and Automata Theory (1971) 129–131.
[6] M. Guignard and K. Spielberg, ”Logical reduction methods in zero–one programming. Minimal preferred inequalities”,Operations Research 29 (1981) 49–74. · Zbl 0452.90044 · doi:10.1287/opre.29.1.49
[7] P.L. Hammer and P. Hansen, ”Logical relations in quadratic 0–1 programming”,Revue Roumaine de Mathématiques Pures et Appliquées 26 (1981) 421–429. · Zbl 0457.90052
[8] P.L. Hammer and S. Nguyen, ”A partial order in the solution space of bivalent programs”, 93–106 in: N. Christofides et al., eds.,Combinatorial optimization (John Wiley & Sons, New York, 1979). · Zbl 0414.90063
[9] P. Hansen, ”A cascade algorithm for the logical closure of a set of binary relations”,Information Processing Letters 5 (1976) 50–55. · Zbl 0327.90021 · doi:10.1016/0020-0190(76)90079-X
[10] P. Hansen and B. Jaumard, ”Uniquely solvable quadratic boolean equations”,Discrete Mathematics 12 (1985) 147–154. · Zbl 0584.06008 · doi:10.1016/0166-218X(85)90068-X
[11] B. Jaumard and M. Minoux, ”An efficient algorithm for the transitive closure and a linear worst case complexity result for a class of sparse graphs”,Information Processing Letters (forthcoming). · Zbl 0592.68063
[12] E.L. Johnson and M.W. Padberg, ”Degree two inequalities, clique facets, and biperfect graphs”,Annals of Discrete Mathematics 16 (1982) 169–187. · Zbl 0523.52009
[13] R. Karp and R.E. Tarjan, ”Linear expected-time algorithms for connectivity problems”,Journal of Algorithms 1 (1980) 374–393. · Zbl 0463.68060 · doi:10.1016/0196-6774(80)90017-6
[14] I. Munro, ”Efficient determination of the transitive closure of a directed graph”,Information Processing Letters 1 (1979) 56–58. · Zbl 0221.68030 · doi:10.1016/0020-0190(71)90006-8
[15] P. Purdom, ”A transitive closure algorithm”,BIT 10 (1970) 76–94. · Zbl 0193.14604 · doi:10.1007/BF01940892
[16] B. Roy, ”Transitivité et connexité”,Compte-rendus de l’Académie des Sciences de Paris 249 (1959) 216–218.
[17] V. Strassen, ”Gaussian elimination is not optimal”,Numerische Mathematik 12 (1969) 354–356. · Zbl 0185.40101 · doi:10.1007/BF02165411
[18] R.E. Tarjan, ”Depth-first search and linear graph algorithms”,SIAM Journal on Computing 1 (1972) 146–160. · Zbl 0251.05107 · doi:10.1137/0201010
[19] S. Warshall, ”A theorem on boolean matrices”,Journal of the Association for Computing Machinery 9 (1962) 11–12. · Zbl 0118.33104
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.