Reducibility as a tool to extend the power of approximation algorithms the minimization of boolean expressions
A. Aiello; E. Burattini; A. Massarotti
RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications (1977)
- Volume: 11, Issue: 1, page 75-82
- ISSN: 0988-3754
Access Full Article
top
How to cite
topAiello, A., Burattini, E., and 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 11.1 (1977): 75-82. <http://eudml.org/doc/92044>.
@article{Aiello1977,
author = {Aiello, A., Burattini, E., Massarotti, A.},
journal = {RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications},
language = {eng},
number = {1},
pages = {75-82},
publisher = {EDP-Sciences},
title = {Reducibility as a tool to extend the power of approximation algorithms the minimization of boolean expressions},
url = {http://eudml.org/doc/92044},
volume = {11},
year = {1977},
}
TY - JOUR
AU - Aiello, A.
AU - Burattini, E.
AU - Massarotti, A.
TI - Reducibility as a tool to extend the power of approximation algorithms the minimization of boolean expressions
JO - RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications
PY - 1977
PB - EDP-Sciences
VL - 11
IS - 1
SP - 75
EP - 82
LA - eng
UR - http://eudml.org/doc/92044
ER -
References
top- 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. Zbl0253.68020
- 2. D. S. JOHNSON, Approximation Algorithms for Combinatorial Problems, Conference Record of Fifth ACM Symposium on Theory of Computing, 1973, p. Zbl0316.68024MR461979
- 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. Zbl0366.68041MR378476
- 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. MR418518
- 5. S. SAHNI, Computational Related Problems, S.I.A.M. J. Comp. 4, 1974, pp. 62-279. Zbl0272.68040MR433985
- 6. S. SAHNI and T. GONZALÈS, P-Complete Problems and Approximate Solutions, Computer Science Dept., University of Minnesota, 1974. MR416113
- 7. J. D. ULLMAN, Polynomial Complete Scheduling Problems, Proc. 4th Symposium on Operating System Principles, 1973, pp. 96-101.
NotesEmbed ?
topYou 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.