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

Y. Crama; P. L. Hammer; B. Jaumard; B. Simeone

RAIRO - Operations Research - Recherche Opérationnelle (1987)

  • Volume: 21, Issue: 4, page 287-305
  • ISSN: 0399-0559

How to cite

top

Crama, Y., et al. "Product form parametric representation of the solutions to a quadratic boolean equation." RAIRO - Operations Research - Recherche Opérationnelle 21.4 (1987): 287-305. <http://eudml.org/doc/104925>.

@article{Crama1987,
author = {Crama, Y., Hammer, P. L., Jaumard, B., Simeone, B.},
journal = {RAIRO - Operations Research - Recherche Opérationnelle},
keywords = {implication graph; transitive closure; parametric representation; consistent quadratic Boolean equation},
language = {eng},
number = {4},
pages = {287-305},
publisher = {EDP-Sciences},
title = {Product form parametric representation of the solutions to a quadratic boolean equation},
url = {http://eudml.org/doc/104925},
volume = {21},
year = {1987},
}

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
PB - EDP-Sciences
VL - 21
IS - 4
SP - 287
EP - 305
LA - eng
KW - implication graph; transitive closure; parametric representation; consistent quadratic Boolean equation
UR - http://eudml.org/doc/104925
ER -

References

top
  1. 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. Zbl0398.68042MR526451
  2. 2. F. BARAHONA, A Solvable Case of Quadratic 0-1 Programming, Discrete Applied Mathematics, Vol. 13, 1986, pp. 23-26. Zbl0597.90059MR829335
  3. 3. C. BERGE, Graphs and Hypergraphs, North-Holland, Amsterdam, 1973. Zbl0254.05101MR357172
  4. 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. Zbl0583.90067MR798006
  5. 5. J. M. BOURJOLLY, An Extension of the König-Egervary Property to Node-weighted Bidirected Graphs, CORR 83-39, University of Waterloo, 1983. Zbl0653.90083
  6. 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. Zbl0567.05031MR780014
  7. 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. Zbl0621.90051MR878776
  8. 8. P. HANSEN and B. JAUMARD, Uniquely Solvable Quadratic Boolean Equations, Discrete Applied Mathematics, Vol. 12, 1985, pp. 147-154. Zbl0584.06008MR808455
  9. 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. Zbl0596.90067MR838481
  10. 10. P. HANSEN and B. SIMEONE, Unimodular Functions, Discrete Applied Mathematics, Vol. 14, 1986, p. 269-281. Zbl0597.90058MR848659
  11. 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. Zbl0358.90021MR471974
  12. 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. 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. Zbl0523.52009MR686306
  14. 14. L. LÖWENHEIM, Uber das Auflösungsproblem im logischen Klassenkalkul, Sitzungsberichte der Berliner Mathematische Gesellschaft, Vol. 7, 1908, pp. 89-94. Zbl39.0089.03JFM39.0089.03
  15. 15. L. LÖWENHEIM, Uber die Auflösung von Gleichungen im logischen Gebietkalkul, Mathematische Annalen, Vol. 68, 1910, pp.169-207. MR1511558JFM41.0088.01
  16. 16. K. MEHLHORN, Data structures and algorithms 2:Graph algorithms and NP-completeness, Springer-Verlag, Berlin, 1984. Zbl0556.68002MR756414
  17. 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. Zbl0461.94015MR596451
  18. 18. J. C. PICARD, Maximal Closure of a Graph and Applications to Combinatorial Problems, Management Science, Vol. 22, 1976, pp. 1268-1272. Zbl0341.05112MR403596
  19. 19. B. ROY, Transitivité et connexité, Compte-rendus de l'Académie des Sciences de Paris, Vol. 249, 1959, pp. 216-218. Zbl0092.15902MR109792
  20. 20. S. RUDEANU, Boolean Functions and Equations, North-Holland, Amsterdam, 1974. Zbl0321.06013MR484821
  21. 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. Zbl0648.05046MR808006
  22. 22. R. E. TARJAN, Depth-first Search and Linear Graph Algorithms, SIAM Journal on Computing, Vol. 1, 1972, pp. 146-160. Zbl0251.05107MR304178
  23. 23. L. G. VALIANT, The Complexity of Enumeration and Reliability Problems, SIAM Journal on Computing, Vol. 8, 1979, pp. 410-421. Zbl0419.68082MR539258
  24. 24. S. WARSHALL, A Theorem on Boolean Matrices, Journal of the Association for Computing Machinery, Vol. 9, 1962, pp.11-12. Zbl0118.33104MR149688

NotesEmbed ?

top

You must be logged in to post comments.

To embed these notes on your page include the following JavaScript code on your page where you want the notes to appear.

Only the controls for the widget will be shown in your chosen language. Notes will be shown in their authored language.

Tells the widget how many notes to show per page. You can cycle through additional notes using the next and previous controls.

    
                

                
Note: Best practice suggests putting the JavaScript code just before the closing </body> tag.