An improved fixed-parameter algorithm for vertex cover

被引：85

作者：

Balasubramanian, R

Fellows, MR

Raman, V

机构：

[1] Inst Math Sci, Madras 600113, Tamil Nadu, India

[2] Univ Victoria, Dept Comp Sci, Victoria, BC, Canada

来源：

INFORMATION PROCESSING LETTERS | 1998年 / 65卷 / 03期

关键词：

algorithms; vertex cover; fixed-parameter tractability;

D O I：

10.1016/S0020-0190(97)00213-5

中图分类号：

TP [自动化技术、计算机技术];

学科分类号：

0812 ;

摘要：

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)(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 Published by Elsevier Science B.V.

引用

页码：163 / 168

页数：6

共 7 条

[1]

[Anonymous], FEASIBLE MATH

[2] NONDETERMINISM WITHIN P [J].