Swapping labeled tokens on graphs

DOI10.1016/j.tcs.2015.01.052zbMath1327.68336OpenAlexW2008048468MaRDI QIDQ2347003

Yoshio Okamoto, Jun Kawahara, Erik D. Demaine, Kei Uchizawa, Takehiro Ito, Katsuhisa Yamanaka, Takeaki Uno, Akira Suzuki, Toshiki Saitoh, Masashi Kiyomi

Publication date: 26 May 2015

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

Full work available at URL: https://hdl.handle.net/1721.1/134490

zbMATH Keywords

treegraph algorithmapproximationcomplete bipartite graphsorting network

Mathematics Subject Classification ID

Trees (05C05) Graph algorithms (graph-theoretic aspects) (05C85) Approximation algorithms (68W25)

Related Items

Swapping Colored Tokens on Graphs ⋮ Sorting on graphs by adjacent swaps using permutation groups ⋮ A simple proof that the \((n^{2} - 1)\)-puzzle is hard ⋮ Shortest Reconfiguration of Perfect Matchings via Alternating Cycles ⋮ The packing number of the double vertex graph of the path graph ⋮ Sequentially Swapping Colored Tokens on Graphs ⋮ How to sort by walking and swapping on paths and trees ⋮ The connectivity of token graphs ⋮ On the Connectivity of Token Graphs of Trees ⋮ Token Swapping on Trees ⋮ Reconfiguration of connected graph partitions ⋮ Improving quantum computation by optimized qubit routing ⋮ Algorithmic theory of qubit routing ⋮ Token shifting on graphs ⋮ Sequentially Swapping Colored Tokens on Graphs ⋮ The Time Complexity of Permutation Routing via Matching, Token Swapping and a Variant ⋮ Swapping colored tokens on graphs ⋮ Unnamed Item ⋮ Complexity of token swapping and its variants ⋮ Hamiltonicity of token graphs of fan graphs ⋮ The edge-connectivity of token graphs ⋮ Connecting the dots (with minimum crossings) ⋮ Computing spectral bounds of the Heisenberg ferromagnet from geometric considerations ⋮ Geometry and Generation of a New Graph Planarity Game ⋮ Introduction to reconfiguration

Cites Work

• Efficient enumeration of all ladder lotteries and its application
• The complexity of finding minimum-length generator sequences
• Axioms and hulls
• Deterministic sorting in nearly logarithmic time on the hypercube and related computers
• An Approximation Algorithm for the Tree t-Spanner Problem on Unweighted Graphs via Generalized Chordal Graphs
• Approximating Minimum Max-Stretch Spanning Trees on Unweighted Graphs
• Sorting on a mesh-connected parallel computer
• Tree Spanners
• Unnamed Item
• Unnamed Item
• Unnamed Item