Faster deterministic algorithm for Cactus Vertex Deletion

被引：0
作者：
Tsur, Dekel [1 ]
机构：
[1] Ben Gurion Univ Negev, Dept Comp Sci, Beer Sheva, Israel
来源：
INFORMATION PROCESSING LETTERS | 2023年 / 179卷
关键词：
Algorithms; Branching algorithms; Graph algorithms; Parameterized complexity;
D O I：
10.1016/j.ipl.2022.106317
中图分类号：
TP [自动化技术、计算机技术];
学科分类号：
0812 ;
摘要：
In the CACTUS VERTEX DELETION (resp., EVEN CYCLE TRANSVERSAL) 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 vertices whose removal from G results in a graph in which every edge belongs to at most one cycle (resp., a graph without even cycles). In this paper we give deterministic O *(13.69k)-time algorithms for CACTUS VERTEX DELETION and EVEN CYCLE TRANSVERSAL.(c) 2022 Elsevier B.V. All rights reserved.
引用
收藏
页数：5
相关论文
共 50 条
  • [31] Parameterized algorithm for eternal vertex cover
    Fomin, Fedor V.
    Gaspers, Serge
    Golovach, Petr A.
    Kratsch, Dieter
    Saurabh, Saket
    INFORMATION PROCESSING LETTERS, 2010, 110 (16) : 702 - 706
  • [32] Deterministic Distributed Vertex Coloring in Polylogarithmic Time
    Barenboim, Leonid
    Elkin, Michael
    JOURNAL OF THE ACM, 2011, 58 (05)
  • [33] APPROXIMATION AND KERNELIZATION FOR CHORDAL VERTEX DELETION
    Jansen, Bart M. P.
    Pilipczuk, Marcin
    SIAM JOURNAL ON DISCRETE MATHEMATICS, 2018, 32 (03) : 2258 - 2301
  • [34] Faster deterministic wakeup in multiple access channels
    De Marco, G
    Pellegrini, M
    Sburlati, G
    THEORETICAL COMPUTER SCIENCE, PROCEEDINGS, 2005, 3701 : 196 - 204
  • [35] Faster deterministic wakeup in multiple access channels
    De Marco, Gianluca
    Pellegrini, Marco
    Sburlati, Giovanni
    DISCRETE APPLIED MATHEMATICS, 2007, 155 (08) : 898 - 903
  • [36] A faster FPT algorithm for Bipartite Contraction
    Guillemot, Sylvain
    Marx, Daniel
    INFORMATION PROCESSING LETTERS, 2013, 113 (22-24) : 906 - 912
  • [37] Cluster Vertex Deletion: A Parameterization between Vertex Cover and Clique-Width
    Doucha, Martin
    Kratochvil, Jan
    MATHEMATICAL FOUNDATIONS OF COMPUTER SCIENCE 2012, 2012, 7464 : 348 - 359
  • [38] A POLYNOMIAL KERNEL FOR PROPER INTERVAL VERTEX DELETION
    Fomin, Fedor V.
    Saurabh, Saket
    Villanger, Yngve
    SIAM JOURNAL ON DISCRETE MATHEMATICS, 2013, 27 (04) : 1964 - 1976
  • [39] On the d-Claw Vertex Deletion Problem
    Hsieh, Sun-Yuan
    Le, Van Bang
    Peng, Sheng-Lung
    COMPUTING AND COMBINATORICS (COCOON 2021), 2021, 13025 : 591 - 603
  • [40] Parameterized Complexity Dichotomy for (r, a)-Vertex Deletion
    Baste, Julien
    Faria, Luerbio
    Klein, Sulamita
    Sau, Ignasi
    THEORY OF COMPUTING SYSTEMS, 2017, 61 (03) : 777 - 794
12345