A 2-approximation NC algorithm for connected vertex cover and tree cover |
| |
Authors: | Toshihiro Fujito Takashi Doi |
| |
Affiliation: | a Graduate School of Information Science, Nagoya University, Furo, Chikusa, Nagoya 464-8603, Japan b Department of Information Electronics, Nagoya University, Furo, Chikusa, Nagoya 464-8603, Japan |
| |
Abstract: | The connected vertex cover problem is a variant of the vertex cover problem, in which a vertex cover is additional required to induce a connected subgraph in a given connected graph. The problem is known to be NP-hard and to be at least as hard to approximate as the vertex cover problem is. While several 2-approximation NC algorithms are known for vertex cover, whether unweighted or weighted, no parallel algorithm with guaranteed approximation is known for connected vertex cover. Moreover, converting the existing sequential 2-approximation algorithms for connected vertex cover to parallel ones results in RNC algorithms of rather high complexity at best.In this paper we present a 2-approximation NC (and RNC) algorithm for connected vertex cover (and tree cover). The NC algorithm runs in O(log2n) time using O(Δ2(m+n)/logn) processors on an EREW-PRAM, while the RNC algorithm runs in O(logn) expected time using O(m+n) processors on a CRCW-PRAM, when a given graph has n vertices and m edges with maximum vertex degree of Δ. |
| |
Keywords: | Approximation algorithms Parallel algorithms Connected vertex cover Tree cover |
本文献已被 ScienceDirect 等数据库收录! |
|