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 条
  • [1] Connected feedback vertex set on AT-free graphs
    Mukherjee, Joydeep
    Saha, Tamojit
    ACTA INFORMATICA, 2025, 62 (01)
  • [2] Feedback vertex set on AT-free graphs
    Kratsch, Dieter
    Mueller, Haiko
    Todinca, Ioan
    DISCRETE APPLIED MATHEMATICS, 2008, 156 (10) : 1936 - 1947
  • [3] BANDWIDTH on AT-free graphs
    Golovach, Petr
    Heggernes, Pinar
    Kratsch, Dieter
    Lokshtanov, Daniel
    Meister, Daniel
    Saurabh, Saket
    THEORETICAL COMPUTER SCIENCE, 2011, 412 (50) : 7001 - 7008
  • [4] FEEDBACK VERTEX SET ON PLANAR GRAPHS
    Chen, Hong-Bin
    Fu, Hung-Lin
    Shih, Chie-Huai
    TAIWANESE JOURNAL OF MATHEMATICS, 2012, 16 (06): : 2077 - 2082
  • [5] Classifying Subset Feedback Vertex Set for H-Free Graphs
    Paesani, Giacomo
    Paulusma, Daniel
    Rzazewski, Pawel
    GRAPH-THEORETIC CONCEPTS IN COMPUTER SCIENCE (WG 2022), 2022, 13453 : 412 - 424
  • [6] Classifying subset feedback vertex set for H-free graphs
    Paesani, Giacomo
    Paulusma, Daniel
    Rzazewski, Pawel
    THEORETICAL COMPUTER SCIENCE, 2024, 1003
  • [7] FPT algorithms for Connected Feedback Vertex Set
    Neeldhara Misra
    Geevarghese Philip
    Venkatesh Raman
    Saket Saurabh
    Somnath Sikdar
    Journal of Combinatorial Optimization, 2012, 24 : 131 - 146
  • [8] FPT algorithms for Connected Feedback Vertex Set
    Misra, Neeldhara
    Philip, Geevarghese
    Raman, Venkatesh
    Saurabh, Saket
    Sikdar, Somnath
    JOURNAL OF COMBINATORIAL OPTIMIZATION, 2012, 24 (02) : 131 - 146
  • [9] The diameter of AT-free graphs
    Ducoffe, Guillaume
    JOURNAL OF GRAPH THEORY, 2022, 99 (04) : 594 - 614
  • [10] Feedback Vertex Set in Alternating Group Graphs
    Wang, Jian
    Xu, Xirong
    Gao, Liqing
    Zhu, Dejun
    Yang, Yuansheng
    UTILITAS MATHEMATICA, 2017, 103 : 237 - 243
12345