An O^*(2.619^k) algorithm for 4-path vertex cover

November 08, 2018 Β· Declared Dead Β· πŸ› Discrete Applied Mathematics

πŸ‘» 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 1811.03592 Category cs.DS: Data Structures & Algorithms Citations 12 Venue Discrete Applied Mathematics Last Checked 4 months ago
Abstract
In the 4-path vertex cover problem, the input is an undirected graph $G$ and an integer $k$. The goal is to decide whether there is a set of vertices $S$ of size at most $k$ such that every path with 4 vertices in $G$ contains at least one vertex of $S$. In this paper we give a parameterized algorithm for 4-path vertex cover whose time complexity is $O^*(2.619^k)$.
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