Back to Search
Start Over
Faster parameterized algorithms for two vertex deletion problems.
- Source :
-
Theoretical Computer Science . Jan2023:Part A, Vol. 940, p112-123. 12p. - Publication Year :
- 2023
-
Abstract
- In the l -Path Vertex Cover problem (resp., the l -Component Order Connectivity problem) the input is an undirected graph G and an integer k. The goal is to decide whether there is a set of vertices of size at most k whose deletion from G results in a graph that does not contain a path with l vertices (resp., does not contain a connected component with at least l vertices). In this paper we give a parameterized algorithm for l -Path Vertex Cover when l = 5 , 6 , 7 , whose running times are O ⁎ (3.945 k) , O ⁎ (4.947 k) , and O ⁎ (5.951 k) , respectively. We also give an algorithm for l -Component Order Connectivity whose running time is O ⁎ ((l − 1 − ϵ l) k) for every l ≥ 4 , where ϵ l > 0 for every l. [ABSTRACT FROM AUTHOR]
- Subjects :
- *ALGORITHMS
*GRAPH algorithms
*INTEGERS
Subjects
Details
- Language :
- English
- ISSN :
- 03043975
- Volume :
- 940
- Database :
- Academic Search Index
- Journal :
- Theoretical Computer Science
- Publication Type :
- Academic Journal
- Accession number :
- 160400923
- Full Text :
- https://doi.org/10.1016/j.tcs.2022.10.044