Sequentially swapping tokens: further on graph classes

DOI10.1016/J.JCSS.2025.103691MaRDI QIDQ6924411zbMATH OpenFDO

Authors Hironori Kiya, Yuto Okada, Hirotaka Ono, Yota Otachi

Publication date 29 September 2025

Published in Journal of Computer and System Sciences (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/J.JCSS.2025.103691

zbMATH Keywords

(generalized) 15-puzzleblock-cactus graphgrid graphKing's graphsequential token swapping

Mathematics Subject Classification ID

Graph algorithms (graph-theoretic aspects) (05C85) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Analysis of algorithms and problem complexity (68Q25) Graph theory (including graph drawing) in computer science (68R10) Combinatorial games (91A46)

Cites work

• A simple proof that the \((n^{2} - 1)\)-puzzle is hard
• Approximation and hardness of token swapping
• Fast Pattern Matching in Strings
• Hamilton Paths in Grid Graphs
• HAMILTONian circuits in chordal bipartite graphs
• Hardness of token swapping on trees
• scientific article; zbMATH DE number 1432797 (Why is no real title available?)
• Intractability of clique-width parameterizations
• Introduction to reconfiguration
• Note on the ``15 puzzle.
• On Steiner’s Problem with Rectilinear Distance
• Parameterized algorithms
• Sequentially swapping colored tokens on graphs
• Steiner trees, connected domination and strongly chordal graphs
• The \((n^ 2-1)\)-puzzle and related relocation problems
• The complexity of change
• The NP-completeness of Steiner tree and dominating set for chordal bipartite graphs
• The Rectilinear Steiner Tree Problem is NP-Complete

This page was built for publication: Sequentially swapping tokens: further on graph classes

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6924411)