An improved fixed-parameter algorithm for vertex cover

Balasubramanian, R. ; Fellows, Michael R. ; Raman, Venkatesh (1998) An improved fixed-parameter algorithm for vertex cover Information Processing Letters, 65 (3). pp. 163-168. ISSN 0020-0190

Full text not available from this repository.

Official URL: http://www.sciencedirect.com/science/article/pii/S...

Related URL: http://dx.doi.org/10.1016/S0020-0190(97)00213-5

Abstract

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 vertices such that every edge of G is incident with at least one of these vertices. We give an algorithm for this problem that runs in time O(kn + (1.324718)kk2). In particular, this gives an O((1.324718)nn2) algorithm to find the minimum vertex cover in the graph.

Item Type:Article
Source:Copyright of this article belongs to Elsevier Science.
Keywords:Algorithms; Vertex Cover; Fixed-parameter Tractability
ID Code:72391
Deposited On:29 Nov 2011 12:44
Last Modified:29 Nov 2011 12:44

Repository Staff Only: item control page