Dekel Tsur
Senior Academic
Faster deterministic algorithms for Co-path Packing and Co-path/cycle Packing
In the Co-path Packing (resp., Co-path/cycle Packing) 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 which is a collection of induced paths (resp., induced paths and cycles). In this paper we give deterministic O∗(3 k) -time algorithms for Co-path Packing and Co-path/cycle Packing.
| Publication language | English |
| Pages | 3701-3710 |
| Journal | Journal of Combinatorial Optimization |
| Volume | 44 |
| Issue number | 5 |
| Publication status | Published - 01.12.2022 |
Keywords
Branching algorithms
Graph algorithms
Parameterized complexity
ASJC Scopus subject areas
Computer Science Applications
Discrete Mathematics and Combinatorics
Control and Optimization
Computational Theory and Mathematics
Applied Mathematics
