Experimental comparison of 2-satisfiability algorithms

Rossella Petreschi; Bruno Simeone

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

  • Volume: 25, Issue: 3, page 241-264
  • ISSN: 0399-0559

How to cite

top

Petreschi, Rossella, and Simeone, Bruno. "Experimental comparison of 2-satisfiability algorithms." RAIRO - Operations Research - Recherche Opérationnelle 25.3 (1991): 241-264. <http://eudml.org/doc/105013>.

@article{Petreschi1991,
author = {Petreschi, Rossella, Simeone, Bruno},
journal = {RAIRO - Operations Research - Recherche Opérationnelle},
keywords = {algorithms; 2-SATISFIABILITY; test problems},
language = {eng},
number = {3},
pages = {241-264},
publisher = {EDP-Sciences},
title = {Experimental comparison of 2-satisfiability algorithms},
url = {http://eudml.org/doc/105013},
volume = {25},
year = {1991},
}

TY - JOUR
AU - Petreschi, Rossella
AU - Simeone, Bruno
TI - Experimental comparison of 2-satisfiability algorithms
JO - RAIRO - Operations Research - Recherche Opérationnelle
PY - 1991
PB - EDP-Sciences
VL - 25
IS - 3
SP - 241
EP - 264
LA - eng
KW - algorithms; 2-SATISFIABILITY; test problems
UR - http://eudml.org/doc/105013
ER -

References

top
  1. 1. A. V. AHO, J. E. HOPCROFT and J. D. ULLMAN, The Design and Analysis of Computer Algorithms, Addison-Wesley, Reading, MA, 1974. Zbl0326.68005MR413592
  2. 2. B. ASPVALL, M. F. PLASS and R. E. TARJAN, A Linear Time Algorithm for Testing the Thrue of Certain Quantified Boolean Formulas, Inf. Proc. Lett., 1979, 8, pp. 121-123. Zbl0398.68042MR526451
  3. 3. S. COOK, The Complexity of Theorem Proving Procedures, Proc. 3rd ACM Symp. on Theory of Comput., 1971, pp. 151-158. Zbl0253.68020
  4. 4. M. DAVIS and H. PUTNAM, A Computing Procedure for Qualification Theory, J. of ACM, 1960, 7, pp. 201-215. Zbl0212.34203MR134439
  5. 5. K. W. DEMING, Independence Numbers of Graphs - an Extension of the Konig-Egervary Property, Discr. Math., 1979, 27, pp. 23-24. Zbl0404.05034
  6. 6. S. EVEN, A. ITAI and A. SHAMIR, On the Complexity of Timetable and Multicomodity flow Problems, SIAM J. Comput., 1976, 5, pp. 691-703. Zbl0358.90021MR471974
  7. 7. F. GAVRIL, Testing for Equality Between Maximum Matching and Minimum Node Covering, Inf. Proc. Lett., 1977, 6, pp. 199-202. Zbl0367.05056MR471429
  8. 8. P. HANSEN, B. JAUMARD and M. MINOUX, Linear Expected-Time Algorithm for Deriving all Logical Conclusion Implied by a set of Boolean Inequalities, Math. Prog., 1986, 34, pp. 223-231. Zbl0596.90067MR838481
  9. 9. R. M. KARP, The Transitive Closure of a Random Digraph, Rondom structures and algorithms, 1990, 1, pp. 73-93. Zbl0712.68076MR1068492
  10. 10. R. PETRESCHI and B. SIMEONE, A Switching Algorithm for the Solution of Quadratic Boolean Equations, Inf. Proc. Lett., 1980, 11, pp. 199-202. Zbl0461.94015MR596451
  11. 11. W. V. QUINE, A Way to Simplifying Truth Functions. Amer. Math. Monthly, 1955, 52, pp. 627-631. Zbl0068.24209MR75886
  12. 12. B. SIMEONE, Quadratic Zero-Uno Programming, Boolean Functions and Graphs, Ph. D. Diss., Univ. of Waterloo, Ontario, 1979. 
  13. 13. B. SIMEONE, Consistency of Quadratic Boolean Equations and the Konig-Egervary Property for Graphs, Ann. Discr. Math., 1985, 25, pp. 281-290. Zbl0648.05046MR808006
  14. 14. R. E. TARJAN, Depth First Search and Linear Graph Algorithms, Siam. J. Comput., 1972, 1, (2), pp. 146-160. Zbl0251.05107MR304178

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.