P. Crescenzi and L. Trevisan,
On the Distributed Decision-Making Complexity of the Minimum
Vertex Cover Problem.
To appear on RAIRO Inf. Theor. Appl., 1996.
Preliminary version in
Proc. 20th Workshop on Graph-Theoretic Concepts in Computer
Science, LNCS 903, 1995, pages 130-139.
The Min Vertex Cover problem is studied under the
distributed decision-making model proposed by Papadimitriou
and Yannakakis in 1991. We prove that in a system formed by
p processors, under a reasonable information regime, the
problem cannot be approximated within a constant ratio smaller
than p, and we provide an algorithm that achieves this optimal