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 条
  • [41] Parameterized Complexity Dichotomy for (r, ℓ)-Vertex Deletion
    Julien Baste
    Luerbio Faria
    Sulamita Klein
    Ignasi Sau
    Theory of Computing Systems, 2017, 61 : 777 - 794
  • [42] Bandwidth Parameterized by Cluster Vertex Deletion Number
    Gima, Tatsuya
    Kim, Eun Jung
    Kohler, Noleen
    Melissinos, Nikolaos
    Vasilakis, Manolis
    ALGORITHMICA, 2025,
  • [43] Faster Parameterized Algorithms for Deletion to Split Graphs
    Esha Ghosh
    Sudeshna Kolay
    Mrinal Kumar
    Pranabendu Misra
    Fahad Panolan
    Ashutosh Rai
    M. S. Ramanujan
    Algorithmica, 2015, 71 : 989 - 1006
  • [44] Faster Parameterized Algorithms for Deletion to Split Graphs
    Ghosh, Esha
    Kolay, Sudeshna
    Kumar, Mrinal
    Misra, Pranabendu
    Panolan, Fahad
    Rai, Ashutosh
    Ramanujan, M. S.
    ALGORITHMICA, 2015, 71 (04) : 989 - 1006
  • [45] Faster Computation of the Maximum Dissociation Set and Minimum 3-Path Vertex Cover in Graphs
    Xiao, Mingyu
    Kou, Shaowei
    FRONTIERS IN ALGORITHMICS (FAW 2015), 2015, 9130 : 282 - 293
  • [46] Parameterized algorithm for 3-path vertex cover
    Tsur, Dekel
    THEORETICAL COMPUTER SCIENCE, 2019, 783 : 1 - 8
  • [47] A Quartic Kernel for Pathwidth-One Vertex Deletion
    Philip, Geevarghese
    Raman, Venkatesh
    Villanger, Yngve
    GRAPH-THEORETIC CONCEPTS IN COMPUTER SCIENCE, 2010, 6410 : 196 - +
  • [48] A Polynomial Kernel for Distance-Hereditary Vertex Deletion
    Eun Jung Kim
    O-joung Kwon
    Algorithmica, 2021, 83 : 2096 - 2141
  • [49] Vertex Deletion Parameterized by Elimination Distance and Even Less
    Jansen, Bart M. P.
    de Kroon, Jari J. H.
    Wlodarczyk, Michal
    STOC '21: PROCEEDINGS OF THE 53RD ANNUAL ACM SIGACT SYMPOSIUM ON THEORY OF COMPUTING, 2021, : 1757 - 1769
  • [50] A Polynomial Kernel for Distance-Hereditary Vertex Deletion
    Kim, Eun Jung
    Kwon, O-joung
    ALGORITHMICA, 2021, 83 (07) : 2096 - 2141
12345