Geodesic
Product form parametric representation of the solutions to a quadratic boolean equation
RAIRO - Operations Research - Recherche Opérationnelle, Tome 21 (1987) no. 4, pp. 287-305.

Voir la notice de l'article provenant de la source Numdam

@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://geodesic.mathdoc.fr/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://geodesic.mathdoc.fr/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://geodesic.mathdoc.fr/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, Tome 21 (1987) no. 4, pp. 287-305. http://geodesic.mathdoc.fr/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. | Zbl | MR

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

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

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

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

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

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

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

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

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

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

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. | MR | JFM

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

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

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

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

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

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

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

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

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