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 条
  • [21] 2-Approximating Feedback Vertex Set in Tournaments
    Lokshtanov, Daniel
    Misra, Pranabendu
    Mukherjee, Joydeep
    Panolan, Fahad
    Philip, Geevarghese
    Saurabh, Saket
    ACM TRANSACTIONS ON ALGORITHMS, 2021, 17 (02)
  • [22] Finite groups whose coprime graphs are AT-free
    Li, Huani
    Ma, Xuanlong
    ELECTRONIC RESEARCH ARCHIVE, 2024, 32 (11): : 6443 - 6449
  • [23] Fixed parameter enumeration algorithm for feedback vertex set in weighted undirected graphs
    Wang J.-X.
    Jiang G.-H.
    Chen J.-E.
    Jisuanji Xuebao/Chinese Journal of Computers, 2010, 33 (07): : 1140 - 1152
  • [24] Computing a Minimum Subset Feedback Vertex Set on Chordal Graphs Parameterized by Leafage
    Papadopoulos, Charis
    Tzimas, Spyridon
    ALGORITHMICA, 2024, 86 (03) : 874 - 906
  • [25] 3-Colouring AT-Free Graphs in Polynomial Time
    Stacho, Juraj
    ALGORITHMICA, 2012, 64 (03) : 384 - 399
  • [26] On the vertex degree indices of connected graphs
    Doslic, Tomislav
    Reti, Tamas
    Vukicevic, Damir
    CHEMICAL PHYSICS LETTERS, 2011, 512 (4-6) : 283 - 286
  • [27] Connected Vertex Covers in Dense Graphs
    Cardinal, Jean
    Levy, Eythan
    APPROXIMATION RANDOMIZATION AND COMBINATORIAL OPTIMIZATION: ALGORITHMS AND TECHNIQUES, PROCEEDINGS, 2008, 5171 : 35 - 48
  • [28] On feedback vertex set in reducible flow hypergraphs
    Faria, Luerbio
    Guedes, Andre L. P.
    Markenzon, Lilian
    PROCEEDINGS OF THE XI LATIN AND AMERICAN ALGORITHMS, GRAPHS AND OPTIMIZATION SYMPOSIUM, 2021, 195 : 212 - 220
  • [29] Connected vertex covers in dense graphs
    Cardinal, Jean
    Levy, Eythan
    THEORETICAL COMPUTER SCIENCE, 2010, 411 (26-28) : 2581 - 2590
  • [30] Feedback vertex set in hypercubes
    Focardi, R
    Luccio, FL
    Peleg, D
    INFORMATION PROCESSING LETTERS, 2000, 76 (1-2) : 1 - 5
12345