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 条
  • [21] On Bounded-Degree Vertex Deletion parameterized by treewidth
    Betzler, Nadja
    Bredereck, Robert
    Niedermeier, Rolf
    Uhlmann, Johannes
    DISCRETE APPLIED MATHEMATICS, 2012, 160 (1-2) : 53 - 60
  • [22] Fixed-Parameter Algorithms for Cluster Vertex Deletion
    Hueffner, Falk
    Komusiewicz, Christian
    Moser, Hannes
    Niedermeier, Rolf
    THEORY OF COMPUTING SYSTEMS, 2010, 47 (01) : 196 - 217
  • [23] Faster deterministic algorithms for CO-PATH PACKING and CO-PATH/CYCLE PACKING
    Tsur, Dekel
    JOURNAL OF COMBINATORIAL OPTIMIZATION, 2022, 44 (05) : 3701 - 3710
  • [24] Faster deterministic algorithms for Co-path Packing and Co-path/cycle Packing
    Dekel Tsur
    Journal of Combinatorial Optimization, 2022, 44 : 3701 - 3710
  • [25] Feedback Vertex Set Inspired Kernel for Chordal Vertex Deletion
    Agrawal, Akanksha
    Lokshtanov, Daniel
    Misra, Pranabendu
    Saurabh, Saket
    Zehavi, Meirav
    ACM TRANSACTIONS ON ALGORITHMS, 2019, 15 (01)
  • [26] Faster Clustering Coefficient Using Vertex Covers
    Green, Oded
    Bader, David A.
    2013 ASE/IEEE INTERNATIONAL CONFERENCE ON SOCIAL COMPUTING (SOCIALCOM), 2013, : 321 - 330
  • [27] On the Complexity of Singly Connected Vertex Deletion
    Das, Avinandan
    Kanesh, Lawqueen
    Madathil, Jayakrishnan
    Muluk, Komal
    Purohit, Nidhi
    Saurabh, Saket
    COMBINATORIAL ALGORITHMS, IWOCA 2020, 2020, 12126 : 237 - 250
  • [28] On the complexity of singly connected vertex deletion
    Das, Avinandan
    Kanesh, Lawqueen
    Madathil, Jayakrishnan
    Muluk, Komal
    Purohit, Nidhi
    Saurabh, Saket
    THEORETICAL COMPUTER SCIENCE, 2022, 934 : 47 - 64
  • [29] Approximation and Kernelization for Chordal Vertex Deletion
    Jansen, Bart M. P.
    Pilipczuk, Marcin
    PROCEEDINGS OF THE TWENTY-EIGHTH ANNUAL ACM-SIAM SYMPOSIUM ON DISCRETE ALGORITHMS, 2017, : 1399 - 1418
  • [30] Polynomial Kernel for Interval Vertex Deletion
    Agrawal, Akanksha
    Lokshtanov, Daniel
    Misra, Pranabendu
    Saurabh, Saket
    Zehavi, Meirav
    ACM TRANSACTIONS ON ALGORITHMS, 2023, 19 (02)
12345