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

How to cite

top

Crescenzi, 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. 1. X. DENG and C. H. PAPADIMITRIOU, Distributed decision-making with incomplete information. In Proceedings of the 12th IFIP Congress, 1992. 
  2. 2. M. R. GAREY and D. S. JOHNSON, Computers and Intractability. A Guide to the Theory of NP-Completeness. Freeman, 1979. Zbl0411.68039MR519066
  3. 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. 4. R. M. KARP, Reducibility among combinatorial problems. In Complexity of Computer Computations. Plenum Press, 1972. Zbl0366.68041MR378476
  5. 5. R. MOTWANI, Lecture notes on approximation algorithms, 1992. 
  6. 6. C. H. PAPADIMITRIOU, The value of information. In Proceedings of World Congress of Economics, 1992. 
  7. 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. 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 ?

top

You 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.

Only the controls for the widget will be shown in your chosen language. Notes will be shown in their authored language.

Tells the widget how many notes to show per page. You can cycle through additional notes using the next and previous controls.

    
                

                
Note: Best practice suggests putting the JavaScript code just before the closing </body> tag.