P. Crescenzi and L. Trevisan,<br> 
<b>On the Distributed Decision-Making Complexity of the Minimum
Vertex Cover Problem</b>.<br>
To appear on <i>RAIRO Inf. Theor. Appl.</i>, 1996.<br>
Preliminary version in 
<i>Proc. 20th Workshop on Graph-Theoretic Concepts in Computer
Science,</i> <b>LNCS</b> 903, 1995, pages 130-139. 



<dl>





<dt> <b> Abstract </b> <dd>

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
        <i>p</i> processors, under a reasonable information regime, the
        problem cannot be approximated within a constant ratio smaller
        than <i>p</i>, and we provide an algorithm that achieves this optimal
        approximation ratio.