Faster deterministic algorithm for Co-Path Set

被引：0
作者：
Tsur, Dekel [1 ]
机构：
[1] Ben Gurion Univ Negev, Dept Comp Sci, Beer Sheva, Israel
来源：
INFORMATION PROCESSING LETTERS | 2023年 / 180卷
关键词：
Graph algorithms; Parameterized complexity; Branching algorithms; RADIATION HYBRID MAP;
D O I：
10.1016/j.ipl.2022.106335
中图分类号：
TP [自动化技术、计算机技术];
学科分类号：
0812 ;
摘要：
In the CO-PATH SET problem, the input is a graph G and an integer k, and the goal is to decide whether there is a set of at most k edges whose removal from G results in a graph in which every connected component is a path. In this paper we give a deterministic O*(2k)-time algorithm for CO-PATH SET.(c) 2022 Elsevier B.V. All rights reserved.
引用
收藏
页数：3
相关论文
共 50 条
  • [41] An improved kernelization algorithm for r-Set Packing
    Abu-Khzam, Faisal N.
    INFORMATION PROCESSING LETTERS, 2010, 110 (16) : 621 - 624
  • [42] A strengthened analysis of an algorithm for DOMINATING SET in planar graphs
    Hagerup, Torben
    DISCRETE APPLIED MATHEMATICS, 2012, 160 (06) : 793 - 798
  • [43] The pair completion algorithm for the homogeneous set sandwich problem
    Bornstein, C
    de Figueiredo, CMH
    de Sá, VGP
    INFORMATION PROCESSING LETTERS, 2006, 98 (03) : 87 - 91
  • [44] An FPT algorithm for edge subset feedback edge set
    Xiao, Mingyu
    Nagamochi, Hiroshi
    INFORMATION PROCESSING LETTERS, 2012, 112 (1-2) : 5 - 9
  • [45] On the longest path algorithm for reconstructing trees from distance matrices
    Reyzin, Lev
    Srivastava, Nikhil
    INFORMATION PROCESSING LETTERS, 2007, 101 (03) : 98 - 100
  • [46] An improved exact algorithm for minimum dominating set in chordal graphs
    Abu-Khzam, Faisal N.
    INFORMATION PROCESSING LETTERS, 2022, 174
  • [47] Efficient Reductions and a Fast Algorithm of Maximum Weighted Independent Set
    Xiao, Mingyu
    Huang, Sen
    Zhou, Yi
    Ding, Bolin
    PROCEEDINGS OF THE WORLD WIDE WEB CONFERENCE 2021 (WWW 2021), 2021, : 3930 - 3940
  • [48] Algorithm to find a maximum 2-packing set in a cactus
    Flores-Lamas, Alejandro
    Alberto Fernandez-Zepeda, Jose
    Antonio Trejo-Sanchez, Joel
    THEORETICAL COMPUTER SCIENCE, 2018, 725 : 31 - 51
  • [49] A randomized BSP/CGM algorithm for the maximal independent set problem
    Ferreira, A
    Schabanel, N
    FOURTH INTERNATIONAL SYMPOSIUM ON PARALLEL ARCHITECTURES, ALGORITHMS, AND NETWORKS (I-SPAN'99), PROCEEDINGS, 1999, : 284 - 289
  • [50] A GENETIC ALGORITHM FOR THE MAXIMUM 2-PACKING SET PROBLEM
    Antonio Trejo-Sanchez, Joel
    Fajardo-Delgado, Daniel
    Octavio Gutierrez-Garcia, J.
    INTERNATIONAL JOURNAL OF APPLIED MATHEMATICS AND COMPUTER SCIENCE, 2020, 30 (01) : 173 - 184
12345