Product form parametric representation of the solutions to a quadratic boolean equation

Free Access

Issue		RAIRO-Oper. Res. Volume 21, Number 4, 1987


Page(s)		287 - 305
DOI		https://doi.org/10.1051/ro/1987210402871
Published online		06 February 2017

1. B. ASPVALL, M. F. PLASS and R. E. TARJAN, A Linear-time Algorithm for Testing the Truth of Certain Quantified Formulas, Information Processing Letters Vol 8, 1979, pp. 121-123. [MR: 526451] [Zbl: 0398.68042] [Google Scholar]
2. F. BARAHONA, A Solvable Case of Quadratic 0-1 Programming, Discrete Applied Mathematics, Vol. 13, 1986, pp. 23-26. [MR: 829335] [Zbl: 0597.90059] [Google Scholar]
3. C. BERGE, Graphs and Hypergraphs, North-Holland, Amsterdam, 1973. [MR: 357172] [Zbl: 0254.05101] [Google Scholar]
4. A. BILLIONNET and M. MINOUX, Maximizing a Supermodular Pseudoboolean Function: a Polynomial Algorithm for Supermodular Cubic Functions, Discrete Applied Mathematics, Vol. 12, 1985, pp. 1-11. [MR: 798006] [Zbl: 0583.90067] [Google Scholar]
5. J. M. BOURJOLLY, An Extension of the König-Egervary Property to Node-weighted Bidirected Graphs, CORR 83-39, University of Waterloo, 1983. [Zbl: 0653.90083] [Google Scholar]
6. C. EBENEGGER, P. L. HAMMER and D. DE WERRA, Pseudo-boolean Functions and Stability of Graphs, Annals of Discrete Mathematics, Vol. 19, 1984, pp. 83-98. [MR: 780014] [Zbl: 0567.05031] [Google Scholar]
7. P. L. HAMMER and B. SIMEONE, Order Relations of variables in 0-1 Programming, Annals of Discrete Mathematics, Vol. 31, 1987, pp. 83-112. [MR: 878776] [Zbl: 0621.90051] [Google Scholar]
8. P. HANSEN and B. JAUMARD, Uniquely Solvable Quadratic Boolean Equations, Discrete Applied Mathematics, Vol. 12, 1985, pp. 147-154. [MR: 808455] [Zbl: 0584.06008] [Google Scholar]
9. P. HANSEN, B. JAUMARD and M. MINOUX, A Linear Expected-time Algorithm for Deriving all Logical Conclusions Implied by a Set of Boolean Inequalities, Mathematical Prograrnming, Vol. 34, 1986, pp. 223-231. [MR: 838481] [Zbl: 0596.90067] [Google Scholar]
10. P. HANSEN and B. SIMEONE, Unimodular Functions, Discrete Applied Mathematics, Vol. 14, 1986, p. 269-281. [MR: 848659] [Zbl: 0597.90058] [Google Scholar]
11. S. EVEN, A. ITAI and A. SHAMIR, On the Complexity of Timetable and Multicommodity Flow Problems, SIAM Journal on Computing, Vol. 5, 1976, pp. 691-703. [MR: 471974] [Zbl: 0358.90021] [Google Scholar]
12. B. JAUMARD, Extraction et utilisation de relations booléennes pour la résolution des programmes linéaires en variables 0-1, Thèse de Doctorat, École Nationale Supérieure des Télécommunications, Paris, 1986. [Google Scholar]
13. E. L. JOHNSON and M. W. PADBERG, Degree two Inequalities, Clique Facets, and Biperfect Graphs, Annals of Discrete Mathematics, Vol. 16, 1982, pp. 169-187. [MR: 686306] [Zbl: 0523.52009] [Google Scholar]
14. L. LÖWENHEIM, Uber das Auflösungsproblem im logischen Klassenkalkul, Sitzungsberichte der Berliner Mathematische Gesellschaft, Vol. 7, 1908, pp. 89-94. [Zbl: 39.0089.03] [JFM: 39.0089.03] [Google Scholar]
15. L. LÖWENHEIM, Uber die Auflösung von Gleichungen im logischen Gebietkalkul, Mathematische Annalen, Vol. 68, 1910, pp.169-207. [EuDML: 158435] [MR: 1511558] [JFM: 41.0088.01] [Google Scholar]
16. K. MEHLHORN, Data structures and algorithms 2:Graph algorithms and NP-completeness, Springer-Verlag, Berlin, 1984. [MR: 756414] [Zbl: 0556.68002] [Google Scholar]
17. R. PETRESCHI and B. SIMEONE, A Switching Algorithm for the Solution of Quadratic Boolean Equations, Information Processing Letters, Vol. 2, 1980, pp.193-198. [MR: 596451] [Zbl: 0461.94015] [Google Scholar]
18. J. C. PICARD, Maximal Closure of a Graph and Applications to Combinatorial Problems, Management Science, Vol. 22, 1976, pp. 1268-1272. [MR: 403596] [Zbl: 0341.05112] [Google Scholar]
19. B. ROY, Transitivité et connexité, Compte-rendus de l'Académie des Sciences de Paris, Vol. 249, 1959, pp. 216-218. [MR: 109792] [Zbl: 0092.15902] [Google Scholar]
20. S. RUDEANU, Boolean Functions and Equations, North-Holland, Amsterdam, 1974. [MR: 484821] [Zbl: 0321.06013] [Google Scholar]
21. B. SIMEONE, Consistency of Quadratic Boolean Equations andthe König-Egerváry Property for Graphs, Annals of Discrete Mathematics, Vol. 25, 1985, pp. 281-290. [MR: 808006] [Zbl: 0648.05046] [Google Scholar]
22. R. E. TARJAN, Depth-first Search and Linear Graph Algorithms, SIAM Journal on Computing, Vol. 1, 1972, pp. 146-160. [MR: 304178] [Zbl: 0251.05107] [Google Scholar]
23. L. G. VALIANT, The Complexity of Enumeration and Reliability Problems, SIAM Journal on Computing, Vol. 8, 1979, pp. 410-421. [MR: 539258] [Zbl: 0419.68082] [Google Scholar]
24. S. WARSHALL, A Theorem on Boolean Matrices, Journal of the Association for Computing Machinery, Vol. 9, 1962, pp.11-12. [MR: 149688] [Zbl: 0118.33104] [Google Scholar]

Current usage metrics show cumulative count of Article Views (full-text article views including HTML views, PDF and ePub downloads, according to the available data) and Abstracts Views on Vision4Press platform.

Data correspond to usage on the plateform after 2015. The current usage metrics is available 48-96 hours after online publication and is updated daily on week days.

Initial download of the metrics may take a while.