Token Swapping on Trees
From MaRDI portal
Publication:6045462
DOI10.46298/dmtcs.8383arXiv1903.06981MaRDI QIDQ6045462
Kshitij Jain, Tillmann Miltzow, Ahmad Biniaz, Zuzana Masárová, Josef Tkadlec, Alexi Turcotte, Unnamed Author, Debajyoti Mondal, Anna Lubiw
Publication date: 31 May 2023
Published in: Discrete Mathematics & Theoretical Computer Science (Search for Journal in Brave)
Full work available at URL: https://arxiv.org/abs/1903.06981
Trees (05C05) Searching and sorting (68P10) Permutations, words, matrices (05A05) Graph theory (including graph drawing) in computer science (68R10) Graphs and abstract algebra (groups, rings, fields, etc.) (05C25)
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Pancake flipping is hard
- Complexity of token swapping and its variants
- The \((n^ 2-1)\)-puzzle and related relocation problems
- Whitney numbers of the second kind for the star poset
- The complexity of finding minimum-length generator sequences
- On inversions and cycles in permutations
- Factoring, into edge transposition of a tree, permutations fixing a terminal vertex
- A linear-time algorithm for the feasibility of pebble motion on trees
- Reduced decompositions of permutations in terms of star transpositions, generalized Catalan numbers and \(k\)-ary trees
- Swapping colored tokens on graphs
- Graph puzzles, homotopy, and the alternating group
- Optimal pebble motion on a tree
- Token graphs
- Multi-color pebble motion on graphs
- Sliding puzzles and rotating puzzles on graphs
- Introduction to reconfiguration
- Diameters of Cayley graphs generated by transposition trees
- Swapping labeled tokens on graphs
- Distance distribution of nodes in star graphs
- Sorting on graphs by adjacent swaps using permutation groups
- How to sort by walking and swapping on paths and trees
- Pebble Games, Proof Complexity, and Time-Space Trade-offs
- ERRATUM: "UPPER BOUNDS FOR SORTING PERMUTATIONS WITH A TRANSPOSITION TREE"
- The complexity of change
- On the Hardness of Optimal Vertex Relabeling and Restricted Vertex Relabeling
- Sequentially Swapping Colored Tokens on Graphs
- The Time Complexity of the Token Swapping Problem and Its Parallel Variants
- Finding the Shortest Move-Sequence in the Graph-Generalized 15-Puzzle Is NP-Hard
- Swapping Colored Tokens on Graphs
- Playing Games with Algorithms: Algorithmic Combinatorial Game Theory
- A group-theoretic model for symmetric interconnection networks
- Multi-agent Pathfinding with n Agents on Graphs with n Vertices: Combinatorial Classification and Tight Algorithmic Bounds
- On the Cost of Interchange Rearrangement in Strings
- Reconfigurations in Graphs and Grids
