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 条
  • [41] The price of connectivity for feedback vertex set
    Belmonte, Remy
    van't Hof, Pim
    Kaminski, Marcin
    Paulusma, Daniel
    DISCRETE APPLIED MATHEMATICS, 2017, 217 : 132 - 143
  • [42] Feedback Vertex Set Inspired Kernel for Chordal Vertex Deletion
    Agrawal, Akanksha
    Lokshtanov, Daniel
    Misra, Pranabendu
    Saurabh, Saket
    Zehavi, Meirav
    PROCEEDINGS OF THE TWENTY-EIGHTH ANNUAL ACM-SIAM SYMPOSIUM ON DISCRETE ALGORITHMS, 2017, : 1383 - 1398
  • [43] A primal-dual interpretation of two 2-approximation algorithms for the feedback vertex set problem in undirected graphs
    Chudak, FA
    Goemans, MX
    Hochbaum, DS
    Williamson, DP
    OPERATIONS RESEARCH LETTERS, 1998, 22 (4-5) : 111 - 118
  • [44] On the feedback vertex set polytope of a series-parallel graph
    Fiorini, Samuel
    Marcotte, Odile
    DISCRETE OPTIMIZATION, 2009, 6 (03) : 271 - 287
  • [45] A Hybrid Immunological Search for the Weighted Feedback Vertex Set Problem
    Cutello, Vincenco
    Oliva, Maria
    Pavone, Mario
    Scollo, Rocco A.
    LEARNING AND INTELLIGENT OPTIMIZATION, LION, 2020, 11968 : 1 - 16
  • [46] Feedback vertex sets on restricted bipartite graphs
    Jiang, Wei
    Liu, Tian
    Wang, Chaoyi
    Xu, Ke
    THEORETICAL COMPUTER SCIENCE, 2013, 507 : 41 - 51
  • [47] PTAS for connected vertex cover in unit disk graphs
    Zhang, Zhao
    Gao, Xiaofeng
    Wu, Weili
    THEORETICAL COMPUTER SCIENCE, 2009, 410 (52) : 5398 - 5402
  • [48] Simple Proof of Hardness of Feedback Vertex Set
    Guruswami, Venkatesan
    Lee, Euiwoong
    THEORY OF COMPUTING, 2016, 12
  • [49] Improved algorithms for feedback vertex set problems
    Chen, Jianer
    Fomin, Fedor V.
    Liu, Yang
    Lu, Songjian
    Villanger, Yngve
    JOURNAL OF COMPUTER AND SYSTEM SCIENCES, 2008, 74 (07) : 1188 - 1198
  • [50] Algorithms for the Independent Feedback Vertex Set Problem
    Tamura, Yuma
    Ito, Takehiro
    Zhou, Xiao
    IEICE TRANSACTIONS ON FUNDAMENTALS OF ELECTRONICS COMMUNICATIONS AND COMPUTER SCIENCES, 2015, E98A (06): : 1179 - 1188
12345