Product form parametric representation of the solutions to a quadratic boolean equation
RAIRO - Operations Research - Recherche Opérationnelle, Volume 21 (1987) no. 4, pp. 287-305.
@article{RO_1987__21_4_287_0,
     author = {Crama, Y. and Hammer, P. L. and Jaumard, B. and Simeone, B.},
     title = {Product form parametric representation of the solutions to a quadratic boolean equation},
     journal = {RAIRO - Operations Research - Recherche Op\'erationnelle},
     pages = {287--305},
     publisher = {EDP-Sciences},
     volume = {21},
     number = {4},
     year = {1987},
     mrnumber = {932181},
     zbl = {0638.90070},
     language = {en},
     url = {http://archive.numdam.org/item/RO_1987__21_4_287_0/}
}
TY  - JOUR
AU  - Crama, Y.
AU  - Hammer, P. L.
AU  - Jaumard, B.
AU  - Simeone, B.
TI  - Product form parametric representation of the solutions to a quadratic boolean equation
JO  - RAIRO - Operations Research - Recherche Opérationnelle
PY  - 1987
SP  - 287
EP  - 305
VL  - 21
IS  - 4
PB  - EDP-Sciences
UR  - http://archive.numdam.org/item/RO_1987__21_4_287_0/
LA  - en
ID  - RO_1987__21_4_287_0
ER  - 
%0 Journal Article
%A Crama, Y.
%A Hammer, P. L.
%A Jaumard, B.
%A Simeone, B.
%T Product form parametric representation of the solutions to a quadratic boolean equation
%J RAIRO - Operations Research - Recherche Opérationnelle
%D 1987
%P 287-305
%V 21
%N 4
%I EDP-Sciences
%U http://archive.numdam.org/item/RO_1987__21_4_287_0/
%G en
%F RO_1987__21_4_287_0
Crama, Y.; Hammer, P. L.; Jaumard, B.; Simeone, B. Product form parametric representation of the solutions to a quadratic boolean equation. RAIRO - Operations Research - Recherche Opérationnelle, Volume 21 (1987) no. 4, pp. 287-305. http://archive.numdam.org/item/RO_1987__21_4_287_0/

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 | Zbl

2. F. Barahona, A Solvable Case of Quadratic 0-1 Programming, Discrete Applied Mathematics, Vol. 13, 1986, pp. 23-26. | MR | Zbl

3. C. Berge, Graphs and Hypergraphs, North-Holland, Amsterdam, 1973. | MR | Zbl

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 | Zbl

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

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 | Zbl

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 | Zbl

8. P. Hansen and B. Jaumard, Uniquely Solvable Quadratic Boolean Equations, Discrete Applied Mathematics, Vol. 12, 1985, pp. 147-154. | MR | Zbl

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 | Zbl

10. P. Hansen and B. Simeone, Unimodular Functions, Discrete Applied Mathematics, Vol. 14, 1986, p. 269-281. | MR | Zbl

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 | Zbl

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.

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 | Zbl

14. L. Löwenheim, Uber das Auflösungsproblem im logischen Klassenkalkul, Sitzungsberichte der Berliner Mathematische Gesellschaft, Vol. 7, 1908, pp. 89-94. | JFM

15. L. Löwenheim, Uber die Auflösung von Gleichungen im logischen Gebietkalkul, Mathematische Annalen, Vol. 68, 1910, pp.169-207. | JFM | MR

16. K. Mehlhorn, Data structures and algorithms 2:Graph algorithms and NP-completeness, Springer-Verlag, Berlin, 1984. | MR | Zbl

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 | Zbl

18. J. C. Picard, Maximal Closure of a Graph and Applications to Combinatorial Problems, Management Science, Vol. 22, 1976, pp. 1268-1272. | MR | Zbl

19. B. Roy, Transitivité et connexité, Compte-rendus de l'Académie des Sciences de Paris, Vol. 249, 1959, pp. 216-218. | MR | Zbl

20. S. Rudeanu, Boolean Functions and Equations, North-Holland, Amsterdam, 1974. | MR | Zbl

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 | Zbl

22. R. E. Tarjan, Depth-first Search and Linear Graph Algorithms, SIAM Journal on Computing, Vol. 1, 1972, pp. 146-160. | MR | Zbl

23. L. G. Valiant, The Complexity of Enumeration and Reliability Problems, SIAM Journal on Computing, Vol. 8, 1979, pp. 410-421. | MR | Zbl

24. S. Warshall, A Theorem on Boolean Matrices, Journal of the Association for Computing Machinery, Vol. 9, 1962, pp.11-12. | MR | Zbl