A 2-approximation parallel algorithm for connected vertex cover problem and tree cover problem

摘要

The connected vertex cover problem and the tree cover problem are respectively the vertex cover problem and the edge dominating set problem with additional requirement of connectivity attached to them. They are known to be NP-complete problems and to have the same approximability. Either problem has been known to be 2-approximable sequentially hut not by an NC(and RNC) algorithm. In this paper, we present a 2-approximation NC (and RNC) algorithm for both problems. The NC algorithm runs in O(log{sup}2 n) time using O(Δ{sup}2(m + n)/log n) processors on an EREW-PRAM, and the RNC algorithm runs in O(log n) expected time using O(m+n) processors on a CRCW-PRAM, when a given graph has n vertices and m edges with maximum degree Δ.