Faster deterministic parameterized algorithm for k-PATH

被引：9
作者：
Tsur, Dekel [1 ]
机构：
[1] Ben Gurion Univ Negev, Dept Comp Sci, Beer Sheva, Israel
来源：
THEORETICAL COMPUTER SCIENCE | 2019年 / 790卷
关键词：
Graph algorithms; k-PATH; Parameterized complexity;
D O I：
10.1016/j.tcs.2019.04.024
中图分类号：
TP301 [理论、方法];
学科分类号：
081202 ;
摘要：
In the k-PATH problem, the input is a directed graph G and an integer k >= 1, and the goal is to decide whether there is a simple directed path in G with exactly k vertices. We give a deterministic algorithm for k-PATH with time complexity 0*(2.554(k)). This improves the previously best deterministic algorithm for this problem of Zehavi [ESA 2015] whose time complexity is O*(2.597(k)). The technique used by our algorithm can also be used to obtain faster deterministic algorithms for k-TREE, r-DIMENSIONAL k-MATCHING, GRAPH MOTIF, and PARTIAL COVER. (C) 2019 Elsevier B.V. All rights reserved.
引用
收藏
页码：96 / 104
页数：9
相关论文
共 50 条
  • [41] Computational experiments with a lazy version of a K quickest simple path ranking algorithm
    M. Pascoal
    M. E. Captivo
    J. C. Clímaco
    TOP, 2007, 15 : 372 - 382
  • [42] Parameterized k-Clustering: Tractability island
    Fomin, Fedor V.
    Golovach, Petr A.
    Simonov, Kirill
    JOURNAL OF COMPUTER AND SYSTEM SCIENCES, 2021, 117 : 50 - 74
  • [43] SUBEXPONENTIAL PARAMETERIZED ALGORITHM FOR MINIMUM FILL-IN
    Fomin, Fedor V.
    Villanger, Yngve
    SIAM JOURNAL ON COMPUTING, 2013, 42 (06) : 2197 - 2216
  • [44] Faster algorithm for optimum Steiner trees
    Vygen, Jens
    INFORMATION PROCESSING LETTERS, 2011, 111 (21-22) : 1075 - 1079
  • [45] A faster FPT algorithm for Bipartite Contraction
    Guillemot, Sylvain
    Marx, Daniel
    INFORMATION PROCESSING LETTERS, 2013, 113 (22-24) : 906 - 912
  • [46] A faster computation of the most vital edge of a shortest path
    Nardelli, E
    Proietti, G
    Widmayer, P
    INFORMATION PROCESSING LETTERS, 2001, 79 (02) : 81 - 85
  • [47] PATH CONTRACTION FASTER THAN 2n
    Agrawal, Akanksha
    Fomin, Fedor V.
    Lokshtanov, Daniel
    Saurabh, Saket
    Tale, Prafullkumar
    SIAM JOURNAL ON DISCRETE MATHEMATICS, 2020, 34 (02) : 1302 - 1325
  • [48] A faster parallel connectivity algorithm on cographs
    Hsieh, Sun-Yuan
    APPLIED MATHEMATICS LETTERS, 2007, 20 (03) : 341 - 344
  • [49] Approximate Counting of k-Paths: Simpler, Deterministic, and in Polynomial Space
    Lokshtanov, Daniel
    Bjorklund, Andreas
    Saurabh, Saket
    Zehavi, Meirav
    ACM TRANSACTIONS ON ALGORITHMS, 2021, 17 (03)
  • [50] A Parameterized Algorithm for Bounded-Degree Vertex Deletion
    Xiao, Mingyu
    COMPUTING AND COMBINATORICS, COCOON 2016, 2016, 9797 : 79 - 91
12345