Faster parameterized algorithm for pumpkin vertex deletion set

January 08, 2019 Β· Declared Dead Β· πŸ› Information Processing Letters

πŸ‘» CAUSE OF DEATH: Ghosted
No code link whatsoever

"No code URL or promise found in abstract"

Evidence collected by the PWNC Scanner

Authors Dekel Tsur arXiv ID 1901.02491 Category cs.DS: Data Structures & Algorithms Citations 3 Venue Information Processing Letters Last Checked 4 months ago
Abstract
A directed graph $G$ is called a pumpkin if $G$ is a union of induced paths with a common start vertex $s$ and a common end vertex $t$, and the internal vertices of every two paths are disjoint. We give an algorithm that given a directed graph $G$ and an integer $k$, decides whether a pumpkin can be obtained from $G$ by deleting at most $k$ vertices. The algorithm runs in $O^*(2^k)$ time.
Community shame:
Not yet rated
Community Contributions

Found the code? Know the venue? Think something is wrong? Let us know!

πŸ“œ Similar Papers

In the same crypt β€” Data Structures & Algorithms

Died the same way β€” πŸ‘» Ghosted