Swapping colored tokens on graphs

DOI10.1016/j.tcs.2018.03.016zbMath1391.68062OpenAlexW3022258227WikidataQ130118343 ScholiaQ130118343MaRDI QIDQ1749531

Katsuhisa Yamanaka, Yushi Uno, Yota Otachi, Toshiki Saitoh, Takashi Horiyama, Ryuhei Uehara, J. Mark Keil, David G. Kirkpatrick

Publication date: 17 May 2018

Published in: Theoretical Computer Science (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.tcs.2018.03.016

zbMATH Keywords

computational complexityNP-completenessfixed-parameter algorithmtoken swappingcolored token swapping

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Coloring of graphs and hypergraphs (05C15) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Graph algorithms (graph-theoretic aspects) (05C85)

Related Items (5)

Shortest Reconfiguration of Perfect Matchings via Alternating Cycles ⋮ Token Swapping on Trees ⋮ Reconfiguration of connected graph partitions ⋮ The Time Complexity of Permutation Routing via Matching, Token Swapping and a Variant ⋮ Cyclic shift problems on graphs

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• The complexity of finding minimum-length generator sequences
• An application of simultaneous diophantine approximation in combinatorial optimization
• Reduced decompositions of permutations in terms of star transpositions, generalized Catalan numbers and \(k\)-ary trees
• Swapping labeled tokens on graphs
• The complexity of change
• The Time Complexity of the Token Swapping Problem and Its Parallel Variants
• Integer Programming with a Fixed Number of Variables
• Graph Layout Problems Parameterized by Vertex Cover
• Planar 3DM is NP-complete
• Minkowski's Convex Body Theorem and Integer Programming
• Parameterized Algorithms

This page was built for publication: Swapping colored tokens on graphs