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
    BUSS, JF
    GOLDSMITH, J
    [J]. SIAM JOURNAL ON COMPUTING, 1993, 22 (03) : 560 - 572
  • [3] Cai L., 1993, Proceedings of the 2nd Israel Symposium on Theory and Computing Systems (Cat. No.93TH0520-7), P118, DOI 10.1109/ISTCS.1993.253478
  • [4] FIXED-PARAMETER TRACTABILITY AND COMPLETENESS .1. BASIC RESULTS
    DOWNEY, RG
    FELLOWS, MR
    [J]. SIAM JOURNAL ON COMPUTING, 1995, 24 (04) : 873 - 921
  • [5] FIXED-PARAMETER TRACTABILITY AND COMPLETENESS .2. ON COMPLETENESS FOR W[1]
    DOWNEY, RG
    FELLOWS, MR
    [J]. THEORETICAL COMPUTER SCIENCE, 1995, 141 (1-2) : 109 - 131
  • [6] MEHLHORN K, 1984, DATA STRUCTURES ALGO, V2
  • [7] On limited nondeterminism and the complexity of the V-C dimension
    Papadimitriou, CH
    Yannakakis, M
    [J]. JOURNAL OF COMPUTER AND SYSTEM SCIENCES, 1996, 53 (02) : 161 - 170
1