On the Parameterized Complexity for Token Jumping on Graphs

DOI10.1007/978-3-319-06089-7_24zbMath1405.68141OpenAlexW318401295MaRDI QIDQ5410654

Katsuhisa Yamanaka, Hirotaka Ono, Ryuhei Uehara, Takehiro Ito, Marcin Kaminski, Akira Suzuki

Publication date: 16 April 2014

Published in: Lecture Notes in Computer Science (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/978-3-319-06089-7_24

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Graph algorithms (graph-theoretic aspects) (05C85) Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) (05C69)

Related Items

Shortest Reconfiguration Paths in the Solution Space of Boolean Formulas ⋮ Reconfiguration of dominating sets ⋮ Reconfiguration on nowhere dense graph classes ⋮ Token sliding on graphs of girth five ⋮ Galactic token sliding ⋮ Parameterized complexity of independent set reconfiguration problems ⋮ Token sliding on graphs of girth five ⋮ Unnamed Item ⋮ On girth and the parameterized complexity of token sliding and Token Jumping ⋮ Linear-time algorithm for sliding tokens on trees ⋮ Reconfiguration on sparse graphs ⋮ On the parameterized complexity of reconfiguration problems ⋮ Unnamed Item ⋮ Incremental optimization of independent sets under the reconfiguration framework ⋮ Independent set reconfiguration parameterized by modular-width ⋮ Token sliding on split graphs ⋮ The Perfect Matching Reconfiguration Problem ⋮ Introduction to reconfiguration