Edit Distances and Factorisations of Even Permutations

DOI10.1007/978-3-540-87744-8_53zbMath1158.68370OpenAlexW2158733432MaRDI QIDQ3541123

Anthony Labarre

Publication date: 25 November 2008

Published in: Algorithms - ESA 2008 (Search for Journal in Brave)

Full work available at URL: https://hal-upec-upem.archives-ouvertes.fr/hal-00728921/file/esa2008.pdf

Mathematics Subject Classification ID

Searching and sorting (68P10) Combinatorics in computer science (68R05)

Related Items (9)

Sorting on graphs by adjacent swaps using permutation groups ⋮ Improved upper bound for sorting permutations by prefix transpositions ⋮ Polynomial-time sortable stacks of burnt pancakes ⋮ Unnamed Item ⋮ The distribution of cycles in breakpoint graphs of signed permutations ⋮ Hamiltonian cycles in unitary prefix transposition rearrangement graphs ⋮ Sorting by Transpositions Is Difficult ⋮ Sorting permutations and binary strings by length-weighted rearrangements ⋮ Bounding prefix transposition distance for strings and permutations

Cites Work

• Sorting permutations by block-interchanges
• The complexity of finding minimum-length generator sequences
• Bounds for sorting by prefix reversal
• Exact and approximation algorithms for sorting by reversals, with application to genome rearrangement
• Symmetry in interconnection networks based on Cayley graphs of permutation groups: A survey
• A group-theoretic model for symmetric interconnection networks
• Sorting Permutations by Reversals and Eulerian Cycle Decompositions
• Sorting by Transpositions
• Unnamed Item
• Unnamed Item

This page was built for publication: Edit Distances and Factorisations of Even Permutations