# On the distributed decision-making complexity of the minimum vertex cover problem

Pierluigi Crescenzi; Luca Trevisan

RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications (1996)

- Volume: 30, Issue: 5, page 431-441
- ISSN: 0988-3754

## Access Full Article

top## How to cite

topCrescenzi, Pierluigi, and Trevisan, Luca. "On the distributed decision-making complexity of the minimum vertex cover problem." RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications 30.5 (1996): 431-441. <http://eudml.org/doc/92544>.

@article{Crescenzi1996,

author = {Crescenzi, Pierluigi, Trevisan, Luca},

journal = {RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications},

keywords = {vertex covers; distributed decision-making model},

language = {eng},

number = {5},

pages = {431-441},

publisher = {EDP-Sciences},

title = {On the distributed decision-making complexity of the minimum vertex cover problem},

url = {http://eudml.org/doc/92544},

volume = {30},

year = {1996},

}

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

PB - EDP-Sciences

VL - 30

IS - 5

SP - 431

EP - 441

LA - eng

KW - vertex covers; distributed decision-making model

UR - http://eudml.org/doc/92544

ER -

## References

top- 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. Zbl0411.68039MR519066
- 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. Zbl0366.68041MR378476
- 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. Zbl1314.91068
- 8. C. H. PAPADIMITRIOU and M. YANNAKAKIS, Linear programming without the matrix. In Proceedings of 25th ACM Symposium on Theory of Computing, 1993. Zbl1310.90073

## NotesEmbed ?

topTo embed these notes on your page include the following JavaScript code on your page where you want the notes to appear.