Connected Feedback Vertex Set on AT-Free Graphs

被引：0
|
作者：
Mukherjee, Joydeep [1 ]
Saha, Tamojit [1 ,2 ]
机构：
[1] Ramakrishna Mission Vivekananda Educ & Res Inst, Howrah, India
[2] TCG CREST, Inst Adv Intelligence, Kolkata, India
来源：
COMBINATORIAL ALGORITHMS, IWOCA 2023 | 2023年 / 13889卷
关键词：
Graph Algorithm; Approximation Algorithm; AT-free graph; Feedback Vertex Set; Combinatorial Optimization; ALGORITHM;
D O I：
10.1007/978-3-031-34347-6_27
中图分类号：
TP301 [理论、方法];
学科分类号：
081202 ;
摘要：
A connected feedback vertex set of a graph is a connected subgraph of the graph whose removal makes the graph cycle free. In this paper, we give an approximation algorithm that computes a connected feedback vertex set of size (1.9091OPT + 6) on 2-connected AT-free graphs with running time O(n(8)m(2)). Also, we give another approximation algorithm that computes a connected feedback vertex set of size (2.9091OPT + 6) on the same graph class with more efficient running time O(min{m(log(n)), n(2)}).
引用
收藏
页码：319 / 330
页数：12
相关论文
共 50 条
  • [31] A note on the geodetic number and the Steiner number of AT-free graphs
    Hon, Wing-Kai
    Kloks, Ton
    Liu, Hsiang-Hsuan
    Wang, Hung-Lung
    Wang, Yue-Li
    THEORETICAL COMPUTER SCIENCE, 2021, 854 : 131 - 135
  • [32] An Immune Metaheuristics for Large Instances of the Weighted Feedback Vertex Set Problem
    Cutello, V.
    Oliva, M.
    Pavone, M.
    Scollo, R. A.
    2019 IEEE SYMPOSIUM SERIES ON COMPUTATIONAL INTELLIGENCE (IEEE SSCI 2019), 2019, : 1928 - 1936
  • [33] Stochastic simulated annealing for directed feedback vertex set
    Russo, Luis M. S.
    Castro, Daniel
    Ilic, Aleksandar
    Romano, Paolo
    Correia, Ana D.
    APPLIED SOFT COMPUTING, 2022, 129
  • [34] Dynamic thresholding search for the feedback vertex set problem
    Sun, Wen
    Hao, Jin-Kao
    Wu, Zihao
    Li, Wenlong
    Wu, Qinghua
    PEERJ COMPUTER SCIENCE, 2023, 9
  • [35] A Cubic Kernel for Feedback Vertex Set and Loop Cutset
    Bodlaender, Hans L.
    van Dijk, Thomas C.
    THEORY OF COMPUTING SYSTEMS, 2010, 46 (03) : 566 - 597
  • [36] A generalization of AT-free graphs and a generic algorithm for solving triangulation problems
    Broersma, HJ
    Kloks, T
    Kratsch, D
    Müller, H
    ALGORITHMICA, 2002, 32 (04) : 594 - 610
  • [37] Faster deterministic FEEDBACK VERTEX SET
    Kociumaka, Tomasz
    Pilipczuk, Marcin
    INFORMATION PROCESSING LETTERS, 2014, 114 (10) : 556 - 560
  • [38] Connected Vertex Cover for (sP1 + P5)-Free Graphs
    Johnson, Matthew
    Paesani, Giacomo
    Paulusma, Daniel
    ALGORITHMICA, 2020, 82 (01) : 20 - 40
  • [39] Parameter Ecology for Feedback Vertex Set
    Jansen, Bart M. P.
    Raman, Venkatesh
    Vatshelle, Martin
    TSINGHUA SCIENCE AND TECHNOLOGY, 2014, 19 (04) : 387 - 409
  • [40] Parameter Ecology for Feedback Vertex Set
    Bart M.P.Jansen
    Venkatesh Raman
    Martin Vatshelle
    TsinghuaScienceandTechnology, 2014, 19 (04) : 387 - 409
12345