A practical method for computing vertex covers for large graphs

The authors present a new heuristic solution technique for the vertex cover problem. This technique is computationally efficient for very large graphs containing thousands of vertices and edges. It is based upon a general heuristic problem solving framework known as parallel dynamic interaction (PDI). A novel aspect of PDI is that it employs an inherently parallel computational structure that is easily implementable on shared memory multiprocessors of modest size. Empirical data indicate that PDI consistently outperforms other reported vertex cover heuristics, including those that require orders of magnitude greater execution time