Faster algorithm for pathwidth one vertex deletion

被引：4

作者：

Tsur, Dekel ^{[1
]}

机构：

[1] Ben Gurion Univ Negev, Dept Comp Sci, Beer Sheva, Israel

来源：

THEORETICAL COMPUTER SCIENCE | 2022年 / 921卷

关键词：

Graph algorithms; Parameterized complexity; Branching algorithms; KERNELS;

D O I：

10.1016/j.tcs.2022.04.001

中图分类号：

TP301 [理论、方法];

学科分类号：

081202 ;

摘要：

In the PATHWIDTH ONE VERTEX DELETION (POVD) 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 with pathwidth at most 1. In this paper we give an algorithm for POVD whose running time is O* (3.888(k)). (c) 2022 Elsevier B.V. All rights reserved.

引用

页码：63 / 74

页数：12

共 10 条

[1] Parameterised Algorithms for Deletion to Classes of DAGs
Agrawal, Akanksha
Saurabh, Saket
Sharma, Roohani
Zehavi, Meirav
[J]. THEORY OF COMPUTING SYSTEMS, 2018, 62 (08) : 1880 - 1909
[2] Kernels for deletion to classes of acyclic digraphs
Agrawal, Akanksha
Saurabh, Saket
Sharma, Roohani
Zehavi, Meirav
[J]. JOURNAL OF COMPUTER AND SYSTEM SCIENCES, 2018, 92 : 9 - 21
[3] ARNBORG S, 1991, LECT NOTES COMPUT SC, V533, P1
[4] Cerven R., 2019, P 44 S MATH FDN COMP
[5] An Improved FPT Algorithm and a Quadratic Kernel for Pathwidth One Vertex Deletion
Cygan, Marek
Pilipczuk, Marcin
Pilipczuk, Michal
Wojtaszczyk, Jakub Onufry
[J]. ALGORITHMICA, 2012, 64 (01) : 170 - 188
[6] Polynomial kernels for deletion to classes of acyclic digraphs
Mnich, Matthias
van Leeuwen, Erik Jan
[J]. DISCRETE OPTIMIZATION, 2017, 25 : 48 - 76
[7] Philip G, 2010, LECT NOTES COMPUT SC, V6410, P196
[8] An O*(2.619k) algorithm for 4-PATH VERTEX COVER
Tsur, Dekel
[J]. DISCRETE APPLIED MATHEMATICS, 2021, 291 : 1 - 14
[9] Parameterized algorithm for 3-path vertex cover
Tsur, Dekel
[J]. THEORETICAL COMPUTER SCIENCE, 2019, 783 : 1 - 8
[10] Faster parameterized algorithm for pumpkin vertex deletion set
Tsur, Dekel
[J]. INFORMATION PROCESSING LETTERS, 2019, 147 : 74 - 76

← 1 →