Sorting on graphs by adjacent swaps using permutation groups

DOI10.1016/j.cosrev.2016.09.003zbMath1398.68116OpenAlexW2523363524MaRDI QIDQ2374257

Dohan Kim

Publication date: 14 December 2016

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

Full work available at URL: https://doi.org/10.1016/j.cosrev.2016.09.003

zbMATH Keywords

permutation grouppermutation sortingadjacent swapobject sortingpermutation decomposition

Mathematics Subject Classification ID

Related Items (4)

Token Swapping on Trees ⋮ Improving quantum computation by optimized qubit routing ⋮ A five-element transformation monoid on labelled trees ⋮ Complexity analysis and performance of double hashing sort algorithm

Uses Software

• GAP
• Magma
• FXT
• hfloat
• libstdc++
• AdjacentSwaps
• GitHub

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Asymptotic normality and combinatorial aspects of the prefix exchange distance distribution
• Minimal sense of direction and decision problems for Cayley graphs
• A combinatorial proof of symmetry among minimal star factorizations
• Sorting permutations by block-interchanges
• A review of metrics on permutations for search landscape analysis
• Whitney numbers of the second kind for the star poset
• Orienting Cayley graphs generated by transposition trees
• Minimal factorizations of permutations into star transpositions
• The complexity of finding minimum-length generator sequences
• On the number of reduced decompositions of elements of Coxeter groups
• Spectra of Cayley graphs
• Bounds for sorting by prefix reversal
• Sorting by bounded block-moves
• Reduced decompositions of permutations in terms of star transpositions, generalized Catalan numbers and \(k\)-ary trees
• The Magma algebra system. I: The user language
• Task assignment in Cayley interconnection topologies
• Enumeration of planar constellations
• Swapping labeled tokens on graphs
• Symmetry in interconnection networks based on Cayley graphs of permutation groups: A survey
• Group-theoretic models of the inversion process in bacterial genomes
• On the construction of all shortest vertex-disjoint paths in Cayley graphs of abelian groups
• A tight upper bound on the number of cyclically adjacent transpositions to sort a permutation
• Lower Bounding Edit Distances between Permutations
• Task swapping networks in distributed systems
• The Reversal Median Problem
• The Design of Approximation Algorithms
• Sorting by Transpositions Is Difficult
• Combinatorics of Coxeter Groups
• Transforming cabbage into turnip
• Swapping Colored Tokens on Graphs
• How to Sort by Walking on a Tree
• Adjacent Swaps on Strings
• Edit Distances and Factorisations of Even Permutations
• Faster algorithms for sorting by transpositions and sorting by block interchanges
• A group-theoretic model for symmetric interconnection networks
• Permutations as Products of Transpositions
• Tree Spanners
• Genome Rearrangements and Sorting by Reversals
• On Some Structural Properties of Star and Pancake Graphs
• Matters Computational
• Codes in Permutations and Error Correction for Rank Modulation
• Algorithms and Data Structures
• On the representation of permutations as products of transpositions

This page was built for publication: Sorting on graphs by adjacent swaps using permutation groups