Swapping Colored Tokens on Graphs

DOI10.1007/978-3-319-21840-3_51zbMath1451.68135arXiv1803.06816OpenAlexW2963428252MaRDI QIDQ3449858

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

Publication date: 30 October 2015

Published in: Lecture Notes in Computer Science (Search for Journal in Brave)

Full work available at URL: https://arxiv.org/abs/1803.06816

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 (8)

Sorting on graphs by adjacent swaps using permutation groups ⋮ Sequentially Swapping Colored Tokens on Graphs ⋮ Token Swapping on Trees ⋮ Token shifting on graphs ⋮ Sequentially Swapping Colored Tokens on Graphs ⋮ The Time Complexity of the Token Swapping Problem and Its Parallel Variants ⋮ Complexity of token swapping and its variants ⋮ Introduction to reconfiguration

Cites Work

• The complexity of finding minimum-length generator sequences
• Reduced decompositions of permutations in terms of star transpositions, generalized Catalan numbers and \(k\)-ary trees
• Swapping labeled tokens on graphs
• Planar 3DM is NP-complete
• Combinatorial optimization. Theory and algorithms
• Unnamed Item
• Unnamed Item

This page was built for publication: Swapping Colored Tokens on Graphs