Complexity of token swapping and its variants
DOI10.1007/S00453-017-0387-0zbMATH Open1393.68068DBLPjournals/algorithmica/BonnetMR18OpenAlexW2767005068WikidataQ59610428 ScholiaQ59610428MaRDI QIDQ722547FDOQ722547
Authors: Édouard Bonnet, Tillmann Miltzow, Paweł Rzążewski 
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
Recommendations
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)
Cites Work
- Which problems have strongly exponential complexity?
- Relationships between nondeterministic and deterministic tape complexities
- Can you beat treewidth?
- Lower bounds based on the exponential time hypothesis
- On the complexity of \(k\)-SAT
- The complexity of completing partial Latin squares
- Clustering to minimize the maximum intercluster distance
- Graph puzzles, homotopy, and the alternating group
- Title not available (Why is that?)
- Sparsity. Graphs, structures, and algorithms
- Title not available (Why is that?)
- Flips in planar graphs
- The NP-completeness of the Hamiltonian cycle problem in planar digraphs with degree bound two
- The NP-Completeness of Some Edge-Partition Problems
- Reduced decompositions of permutations in terms of star transpositions, generalized Catalan numbers and \(k\)-ary trees
- Reconfigurations in Graphs and Grids
- Linear-time algorithm for sliding tokens on trees
- Classes of Pebble Games and Complete Problems
- Token graphs
- Swapping labeled tokens on graphs
- Swapping Colored Tokens on Graphs
- Subexponential time algorithms for finding small tree and path decompositions
- How to sort by walking on a tree
- Sliding token on bipartite permutation graphs
- Approximation and hardness of token swapping
- Complexity of token swapping and its variants
- Sorting of Permutations by Cost-Constrained Transpositions
Cited In (18)
- The parameterized complexity of finding point sets with hereditary properties
- The time complexity of the token swapping problem and its parallel variants
- Sequentially swapping colored tokens on graphs
- On a compact encoding of the swap automaton
- Swapping colored tokens on graphs
- Shortest reconfiguration of perfect matchings via alternating cycles
- Complexity of token swapping and its variants
- Reconfiguration of connected graph partitions
- Algorithmic theory of qubit routing
- On the diameters of friends-and-strangers graphs
- Title not available (Why is that?)
- Approximation and hardness of token swapping
- Multivariate complexity analysis of Swap Bribery
- Title not available (Why is that?)
- Token Swapping on Trees
- Sequentially swapping tokens: further on graph classes
- The time complexity of permutation routing via matching, token swapping and a variant
- Polynomial time algorithms for the token swapping problem on cographs
This page was built for publication: Complexity of token swapping and its variants
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q722547)
