Dekel Tsur
Senior Academic
Faster deterministic algorithm for Co-Path Set
In the CO-PATH SET 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 edges whose removal from G results in a graph in which every connected component is a path. In this paper we give a deterministic O⁎(2k)-time algorithm for CO-PATH SET.
| Publication language | English |
| Journal | Information Processing Letters |
| Volume | 180 |
| Publication status | Published - 01.02.2023 |
| Article Number | 106335 |
Keywords
Branching algorithms
Graph algorithms
Parameterized complexity
ASJC Scopus subject areas
Theoretical Computer Science
Signal Processing
Information Systems
Computer Science Applications
