The VERTEX COVER problem asks, for input consisting of a graph G on n
vertices, and a positive integer k, whether there is a set of k vertic
es such that every edge of G is incident with at least one of these ve
rtices. We give an algorithm for this problem that runs in time O(kn (1.324718)(k)k(2)). In particular, this gives an O((1.324718)(n)n(2))
algorithm to find the minimum vertex cover in the graph. (C) 1998 Pub
lished by Elsevier Science B.V.