Complexity of token swapping and its variants

DOI10.1007/s00453-017-0387-0zbMath1393.68068OpenAlexW2767005068WikidataQ59610428 ScholiaQ59610428MaRDI QIDQ722547

Paweł Rzążewski, Tillmann Miltzow, Édouard Bonnet

Publication date: 26 July 2018

Published in: Algorithmica (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/s00453-017-0387-0

zbMATH Keywords

parameterized complexityW[1-hardness]token swapping

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Graph theory (including graph drawing) in computer science (68R10) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17)

Related Items

Shortest Reconfiguration of Perfect Matchings via Alternating Cycles ⋮ Sequentially Swapping Colored Tokens on Graphs ⋮ Token Swapping on Trees ⋮ Reconfiguration of connected graph partitions ⋮ Algorithmic theory of qubit routing ⋮ The Time Complexity of Permutation Routing via Matching, Token Swapping and a Variant ⋮ The Parameterized Complexity of Finding Point Sets with Hereditary Properties ⋮ Unnamed Item ⋮ Unnamed Item

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Sparsity. Graphs, structures, and algorithms
• Linear-time algorithm for sliding tokens on trees
• The complexity of completing partial Latin squares
• Flips in planar graphs
• Clustering to minimize the maximum intercluster distance
• The NP-completeness of the Hamiltonian cycle problem in planar digraphs with degree bound two
• Reduced decompositions of permutations in terms of star transpositions, generalized Catalan numbers and \(k\)-ary trees
• Which problems have strongly exponential complexity?
• Graph puzzles, homotopy, and the alternating group
• Token graphs
• Swapping labeled tokens on graphs
• Relationships between nondeterministic and deterministic tape complexities
• Swapping Colored Tokens on Graphs
• Subexponential Time Algorithms for Finding Small Tree and Path Decompositions
• How to Sort by Walking on a Tree
• Optimal Parameterized Algorithms for Planar Facility Location Problems Using Voronoi Diagrams
• Sliding Token on Bipartite Permutation Graphs
• Classes of Pebble Games and Complete Problems
• The NP-Completeness of Some Edge-Partition Problems
• Deciding First-Order Properties of Nowhere Dense Graphs
• Sorting of Permutations by Cost-Constrained Transpositions
• Reconfigurations in Graphs and Grids
• On the complexity of \(k\)-SAT

This page was built for publication: Complexity of token swapping and its variants