Reducibility as a tool to extend the power of approximation algorithms the minimization of boolean expressions
Aiello, A. ; Burattini, E. ; Massarotti, A.
RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications, Tome 11 (1977), p. 75-82 / Harvested from Numdam
Access to full text
Full (PDF)
Full (DJVU)
Publié le : 1977-01-01
@article{ITA_1977__11_1_75_0,
     author = {Aiello, A. and Burattini, E. and Massarotti, A.},
     title = {Reducibility as a tool to extend the power of approximation algorithms the minimization of boolean expressions},
     journal = {RAIRO - Theoretical Informatics and Applications - Informatique Th\'eorique et Applications},
     volume = {11},
     year = {1977},
     pages = {75-82},
     mrnumber = {478742},
     zbl = {0366.94048},
     language = {en},
     url = {http://dml.mathdoc.fr/item/ITA_1977__11_1_75_0}
}

Aiello, A.; Burattini, E.; Massarotti, A. Reducibility as a tool to extend the power of approximation algorithms the minimization of boolean expressions. RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications, Tome 11 (1977) pp. 75-82. http://gdmltest.u-ga.fr/item/ITA_1977__11_1_75_0/

1. S. Cook, The Complexity of Theorem Proving Procedures, Proc. 3rd Annual ACM Symposium on Theory of Computing, 1971, pp. 151-158. p. 38-49. | Zbl 0253.68020

2. D. S. Johnson, Approximation Algorithms for Combinatorial Problems, Conference Record of Fifth ACM Symposium on Theory of Computing, 1973, p. | MR 461979 | Zbl 0316.68024

3. R. M. Karp, Reducibility Among Combinatorial Problems, In Complexity of Computer Computations, R. E. MILLER and J. W. THATCHER Eds and Plenum Press, New York, 1972, pp. 85-104. | MR 378476 | Zbl 0366.68041

4. A. R. Meyer and L. Stockmeyer, Non Elementary Word Problems in Automata and Logic, Proc. AMS Symposium on Complexity of Computation, 1973, pp. 38-49. | MR 418518

5. S. Sahni, Computational Related Problems, S.I.A.M. J. Comp. 4, 1974, pp. 62-279. | MR 433985 | Zbl 0272.68040

6. S. Sahni and T. Gonzalès, P-Complete Problems and Approximate Solutions, Computer Science Dept., University of Minnesota, 1974. | MR 416113

7. J. D. Ullman, Polynomial Complete Scheduling Problems, Proc. 4th Symposium on Operating System Principles, 1973, pp. 96-101.