A simple quadratic kernel for Token Jumping on surfaces

August 08, 2024 Β· Declared Dead Β· πŸ› International Workshop on Graph-Theoretic Concepts in Computer Science

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

"No code URL or promise found in abstract"

Evidence collected by the PWNC Scanner

Authors Daniel W. Cranston, Moritz MΓΌhlenthaler, Benjamin Peyrille arXiv ID 2408.04743 Category cs.DS: Data Structures & Algorithms Cross-listed cs.DM Citations 1 Venue International Workshop on Graph-Theoretic Concepts in Computer Science Last Checked 4 months ago
Abstract
The problem \textsc{Token Jumping} asks whether, given a graph $G$ and two independent sets of \emph{tokens} $I$ and $J$ of $G$, we can transform $I$ into $J$ by changing the position of a single token in each step and having an independent set of tokens throughout. We show that there is a polynomial-time algorithm that, given an instance of \textsc{Token Jumping}, computes an equivalent instance of size $O(g^2 + gk + k^2)$, where $g$ is the genus of the input graph and $k$ is the size of the independent sets.
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