A 2-approximation NC algorithm for connected vertex cover and tree cover.

Toshihiro Fujito Takashi Doi

Published in: Inf. Process. Lett. (2004)

Keyphrases

vertex cover
approximation algorithms
learning algorithm
dynamic programming
tree structure
optimal solution
np hard
expectation maximization
theoretical analysis
approximation ratio
worst case
search space
minimum spanning tree
polynomial time approximation