K. L.Clarkson. A Randomized Parallel Algorithm for Weighted Vertex Cover. Unpublished, 1987.
This paper gives a parallel algorithm for solving the following problem: a simple undirected graph G with vertex set V of size n, edge set E of size m, and weight function w:V -> R+ is given. Find a set of vertices C such that every edge in E is covered by a vertex of C (meets that vertex), and the weight w(C)= sumx in C wx is small. The algorithm returns a cover with a weight that is within a factor of two of the minimum possible, matching several previous algorithms. If the vertex weights are k-bit integers, the algorithm requires expected O(log3nlog K) time with mKO(1) processors on a EREW PRAM, where K=O(k+log n), so the weighted vertex cover problem is in RNC.