On the distributed decision-making complexity of the minimum vertex cover problem
Crescenzi, Pierluigi ; Trevisan, Luca
RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications, Tome 30 (1996), p. 431-441 / Harvested from Numdam
Access to full text
Full (PDF)
Full (DJVU)
Publié le : 1996-01-01
@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},
     volume = {30},
     year = {1996},
     pages = {431-441},
     mrnumber = {1435731},
     zbl = {0876.68101},
     language = {en},
     url = {http://dml.mathdoc.fr/item/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) pp. 431-441. http://gdmltest.u-ga.fr/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 519066 | Zbl 0411.68039

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 378476 | Zbl 0366.68041

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.