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
