Sequentially swapping tokens: Further on graph classes
Authors:
- Hironori KiyaHKHironori Kiya
- Yuto OkadaYOYuto Okada
- Hirotaka OnoHOHirotaka Ono
- Yota OtachiYOYota Otachi
- 17 July 2025
- journal article
- Published by Elsevier in Journal of Computer and System Sciences
- Vol. 155
Abstract
No abstract availableFunding Information
- Japan Society for the Promotion of Science (JP21K21283, JP21K19765, JP20H05793, JP18H04091, JP21K11752, JP17K19960, JP20H05967, JP22H00513, JP17H01698)
This publication has 15 references indexed in Scilit:
- A simple proof that the (n2 − 1)-puzzle is hardTheoretical Computer Science, 2018
- Width Parameters Beyond Tree-width and their ApplicationsThe Computer Journal, 2007
- Hamiltonian circuits in chordal bipartite graphsDiscrete Mathematics, 1996
- The (n2−1)-puzzle and related relocation problemsJournal of Symbolic Computation, 1990
- The NP-completeness of steiner tree and dominating set for chordal bipartite graphsTheoretical Computer Science, 1987
- Steiner trees, connected domination and strongly chordal graphsNetworks, 1985
- Hamilton Paths in Grid GraphsSIAM Journal on Computing, 1982
- Fast Pattern Matching in StringsSIAM Journal on Computing, 1977
- The Rectilinear Steiner Tree Problem is $NP$-CompleteSIAM Journal on Applied Mathematics, 1977
- On Steiner’s Problem with Rectilinear DistanceSIAM Journal on Applied Mathematics, 1966