Short proofs for cut-and-paste sorting of permutations

DOI10.1016/j.disc.2007.01.011zbMath1128.05001arXivmath/0605084OpenAlexW2137640073MaRDI QIDQ2461214

Ivan Hal Sudborough, Douglas B. West, Daniel W. Cranston

Publication date: 27 November 2007

Published in: Discrete Mathematics (Search for Journal in Brave)

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

zbMATH Keywords

sortingpermutationtranspositionreversalcut-and-paste

Mathematics Subject Classification ID

Permutations, words, matrices (05A05)

Related Items (7)

A NOTE ON COMPLEXITY OF GENETIC MUTATIONS ⋮ Sorting by shuffling methods and a queue ⋮ A 2.25-Approximation Algorithm for Cut-and-Paste Sorting of Unsigned Circular Permutations ⋮ A new approximation algorithm for cut-and-paste sorting of unsigned circular permutations ⋮ CIRCULAR INVERSIONS OF PERMUTATIONS AND THEIR USE IN SORTING PROBLEMS ⋮ On the effective and automatic enumeration of polynomial permutation classes ⋮ Bounding prefix transposition distance for strings and permutations

Cites Work

• Unnamed Item
• Unnamed Item
• Sorting by insertion of leading elements
• Bounds for sorting by prefix reversal
• On the problem of sorting burnt pancakes
• A Simpler 1.5-Approximation Algorithm for Sorting by Transpositions
• On the Diameter of the Pancake Network
• Sorting a bridge hand

This page was built for publication: Short proofs for cut-and-paste sorting of permutations