On the distributed decision-making complexity of the minimum vertex cover problem
RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications, Tome 30 (1996) no. 5, pp. 431-441. 
@article{ITA_1996__30_5_431_0,
     author = {Crescenzi, Pierluigi and Trevisan, Luca},
     title = {On the distributed decision-making complexity of the minimum vertex cover problem},
     journal = {RAIRO - Theoretical Informatics and Applications - Informatique Th\'eorique et Applications},
     pages = {431--441},
     publisher = {EDP-Sciences},
     volume = {30},
     number = {5},
     year = {1996},
     mrnumber = {1435731},
     zbl = {0876.68101},
     language = {en},
     url = {http://archive.numdam.org/item/ITA_1996__30_5_431_0/}
}
TY  - JOUR
AU  - Crescenzi, Pierluigi
AU  - Trevisan, Luca
TI  - On the distributed decision-making complexity of the minimum vertex cover problem
JO  - RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications
PY  - 1996
SP  - 431
EP  - 441
VL  - 30
IS  - 5
PB  - EDP-Sciences
UR  - http://archive.numdam.org/item/ITA_1996__30_5_431_0/
LA  - en
ID  - ITA_1996__30_5_431_0
ER  - 
%0 Journal Article
%A Crescenzi, Pierluigi
%A Trevisan, Luca
%T On the distributed decision-making complexity of the minimum vertex cover problem
%J RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications
%D 1996
%P 431-441
%V 30
%N 5
%I EDP-Sciences
%U http://archive.numdam.org/item/ITA_1996__30_5_431_0/
%G en
%F ITA_1996__30_5_431_0
Crescenzi, Pierluigi; Trevisan, Luca. On the distributed decision-making complexity of the minimum vertex cover problem. RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications, Tome 30 (1996) no. 5, pp. 431-441. http://archive.numdam.org/item/ITA_1996__30_5_431_0/

1. X. Deng and C. H. Papadimitriou, Distributed decision-making with incomplete information. In Proceedings of the 12th IFIP Congress, 1992.

2. M. R. Garey and D. S. Johnson, Computers and Intractability. A Guide to the Theory of NP-Completeness. Freeman, 1979. | MR | Zbl

3. S. Irani and Y. Rabani, On the value of information in coordination games. In Proceedings of the 34th IEEE Symposium of Foundations of Computer Science, 1993, pp. 12-21. An extended version is to appear in the SIAM Journal of Computing.

4. R. M. Karp, Reducibility among combinatorial problems. In Complexity of Computer Computations. Plenum Press, 1972. | MR | Zbl

5. R. Motwani, Lecture notes on approximation algorithms, 1992.

6. C. H. Papadimitriou, The value of information. In Proceedings of World Congress of Economics, 1992.

7. C. H. Papadimitriou and M. Yannakakis, On the value of information in distributed decision making. In Proceedings of 10th ACM Symposium on Principles of Distributed Computing, 1991, pp. 61-64.

8. C. H. Papadimitriou and M. Yannakakis, Linear programming without the matrix. In Proceedings of 25th ACM Symposium on Theory of Computing, 1993.