Complexity of token swapping and its variants

DOI10.1007/S00453-017-0387-0MaRDI QIDQ722547zbMATH OpenOpenAlexDBLPWikidataFDO

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

Publication date 26 July 2018

Published in Algorithmica (Search for Journal in Brave)

Copyright license Creative Commons Attribution 4.0 International

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)

Recommendations

• Complexity of token swapping and its variants
• Approximation and hardness of token swapping
• Swapping colored tokens on graphs
• Swapping Colored Tokens on Graphs
• The time complexity of the token swapping problem and its parallel variants

Cites work

• scientific article; zbMATH DE number 3761989 (Why is no real title available?)
• scientific article; zbMATH DE number 1433426 (Why is no real title available?)
• Approximation and hardness of token swapping
• Can you beat treewidth?
• Classes of Pebble Games and Complete Problems
• Clustering to minimize the maximum intercluster distance
• Complexity of token swapping and its variants
• Flips in planar graphs
• Graph puzzles, homotopy, and the alternating group
• How to sort by walking on a tree
• Linear-time algorithm for sliding tokens on trees
• Lower bounds based on the exponential time hypothesis
• On the complexity of \(k\)-SAT
• Reconfigurations in Graphs and Grids
• Reduced decompositions of permutations in terms of star transpositions, generalized Catalan numbers and k-ary trees
• Relationships between nondeterministic and deterministic tape complexities
• Sliding token on bipartite permutation graphs
• Sorting of Permutations by Cost-Constrained Transpositions
• Sparsity. Graphs, structures, and algorithms
• Subexponential time algorithms for finding small tree and path decompositions
• Swapping Colored Tokens on Graphs
• Swapping labeled tokens on graphs
• The NP-Completeness of Some Edge-Partition Problems
• The NP-completeness of the Hamiltonian cycle problem in planar digraphs with degree bound two
• The complexity of completing partial Latin squares
• Token graphs
• Which problems have strongly exponential complexity?

Cited in

(18)

• The time complexity of permutation routing via matching, token swapping and a variant
• Polynomial time algorithms for the token swapping problem on cographs
• 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
• scientific article; zbMATH DE number 7559366 (Why is no real title available?)
• Approximation and hardness of token swapping
• Multivariate complexity analysis of Swap Bribery
• scientific article; zbMATH DE number 7559364 (Why is no real title available?)
• Token Swapping on Trees
• Sequentially swapping tokens: further on graph classes

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)