Complexity of token swapping and its variants

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

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

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 complexity; W[1-hardness]; token swapping

Mathematics Subject Classification ID

68Q25: Analysis of algorithms and problem complexity

68R10: Graph theory (including graph drawing) in computer science

68Q17: Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.)