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 条
  • [21] A faster parameterized algorithm for temporal matching
    Zschoche, Philipp
    INFORMATION PROCESSING LETTERS, 2022, 174
  • [22] A faster parallel connectivity algorithm on cographs
    Hsieh, Sun-Yuan
    APPLIED MATHEMATICS LETTERS, 2007, 20 (03) : 341 - 344
  • [23] A faster FPT algorithm for Bipartite Contraction
    Guillemot, Sylvain
    Marx, Daniel
    INFORMATION PROCESSING LETTERS, 2013, 113 (22-24) : 906 - 912
  • [24] A faster parameterized algorithm for PSEUDOFOREST DELETION
    Bodlaender, Hans L.
    Ono, Hirotaka
    Otachi, Yota
    DISCRETE APPLIED MATHEMATICS, 2018, 236 : 42 - 56
  • [25] A FASTER PARAMETRIC MINIMUM-CUT ALGORITHM
    GUSFIELD, D
    TARDOS, E
    ALGORITHMICA, 1994, 11 (03) : 278 - 290
  • [26] Parameterized algorithm for 3-path vertex cover
    Tsur, Dekel
    THEORETICAL COMPUTER SCIENCE, 2019, 783 : 1 - 8
  • [27] A Parametric Polynomial Deterministic Algorithm for #2SAT
    Raymundo Marcial-Romero, J.
    De Ita Luna, Guillermo
    Antonio Hernandez, J.
    Maria Valdovinos, Rosa
    ADVANCES IN ARTIFICIAL INTELLIGENCE AND SOFT COMPUTING, MICAI 2015, PT I, 2015, 9413 : 202 - 213
  • [28] A Faster Algorithm for Computing the Girth of Planar and Bounded Genus Graphs
    Djidjev, Hristo N.
    ACM TRANSACTIONS ON ALGORITHMS, 2010, 7 (01)
  • [29] A faster algorithm for the cluster editing problem on proper interval graphs
    Chih Lin, Min
    Soulignac, Francisco J.
    Szwarcfiter, Jayme L.
    INFORMATION PROCESSING LETTERS, 2015, 115 (12) : 913 - 916
  • [30] An Efficient Algorithm for Power Dominating Set
    Blaesius, Thomas
    Goettlicher, Max
    ALGORITHMICA, 2025, 87 (03) : 344 - 376
12345