Shortest Reconfiguration of Sliding Tokens on a Caterpillar

DOI10.1007/978-3-319-30139-6_19zbMath1475.68254arXiv1511.00243OpenAlexW2258225879MaRDI QIDQ2803826

Takeshi Yamada, Ryuhei Uehara

Publication date: 3 May 2016

Published in: WALCOM: Algorithms and Computation (Search for Journal in Brave)

Full work available at URL: https://arxiv.org/abs/1511.00243

Mathematics Subject Classification ID

Analysis of algorithms (68W40) Graph theory (including graph drawing) in computer science (68R10) Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) (05C69)

Related Items (4)

Parameterized complexity of independent set reconfiguration problems ⋮ Reconfiguration of cliques in a graph ⋮ Shortest Reconfiguration of Sliding Tokens on a Caterpillar ⋮ Introduction to reconfiguration

Cites Work

• Unnamed Item
• Complexity of independent set reconfigurability problems
• Linear-time algorithm for sliding tokens on trees
• On the parameterized complexity of reconfiguration problems
• On the complexity of reconfiguration problems
• An exact algorithm for the Boolean connectivity problem for \(k\)-CNF
• The \((n^ 2-1)\)-puzzle and related relocation problems
• PSPACE-completeness of sliding-block puzzles and other problems through the nondeterministic constraint logic model of computation
• Shortest Reconfiguration of Sliding Tokens on a Caterpillar
• Reconfiguration over Tree Decompositions
• Reconfiguring Independent Sets in Claw-Free Graphs
• Shortest Reconfiguration Paths in the Solution Space of Boolean Formulas
• Sliding Token on Bipartite Permutation Graphs
• An Incremental Linear-Time Algorithm for Recognizing Interval Graphs
• Graph Classes: A Survey
• Linear-Time Representation Algorithms for Proper Circular-Arc Graphs and Proper Interval Graphs
• The Connectivity of Boolean Satisfiability: Computational and Structural Dichotomies

This page was built for publication: Shortest Reconfiguration of Sliding Tokens on a Caterpillar