AN IMPROVED FIXED-PARAMETER ALGORITHM FOR VERTEX COVER

Authors
BALASUBRAMANIAN R FELLOWS MR RAMAN V
Citation
R. Balasubramanian et al., AN IMPROVED FIXED-PARAMETER ALGORITHM FOR VERTEX COVER, Information processing letters, 65(3), 1998, pp. 163-168
Citations number
7
Categorie Soggetti
Computer Science Information Systems","Computer Science Information Systems
Journal title
Information processing letters → ACNP
ISSN journal
00200190
Volume
65
Issue
3
Year of publication
1998
Pages
163 - 168
Database
ISI
SICI code
0020-0190(1998)65:3<163:AIFAFV>2.0.ZU;2-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 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.