An (18/11)n upper bound for sorting by prefix reversals

DOI10.1016/J.TCS.2008.04.045MaRDI QIDQ838149zbMATH OpenOpenAlexDBLPWikidataFDO

Authors N. E. Zubov

Publication date 21 August 2009

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

Full work available at URL https://doi.org/10.1016/j.tcs.2008.04.045

zbMATH Keywords

permutationsupper boundspancake problempancake networksorting by prefix reversals

Mathematics Subject Classification ID

Searching and sorting (68P10)

Recommendations

• On the problem of sorting burnt pancakes
• Pancake flipping and sorting permutations
• On the Diameter of the Pancake Network

Cites work

• scientific article; zbMATH DE number 2024859 (Why is no real title available?)
• A group-theoretic model for symmetric interconnection networks
• Bounds for sorting by prefix reversal
• On the Diameter of the Pancake Network
• On the problem of sorting burnt pancakes

Cited in

(25)

• Upper bounds for sorting permutations with a transposition tree
• A quadratic lower bound for topswops
• Presentations of Coxeter groups of type \(A, B\), and \(D\) using prefix-reversal generators
• Sorting permutations and binary strings by length-weighted rearrangements
• Some relations on prefix reversal generators of the symmetric and hyperoctahedral group
• Cycles in the burnt pancake graph
• The spectral gap of graphs arising from substring reversals
• An audit tool for genome rearrangement algorithms
• On average and highest number of flips in pancake sorting
• An Algorithm to Enumerate Grid Signed Permutation Classes
• Successor rules for flipping pancakes and burnt pancakes
• Physical zero-knowledge proof protocol for Topswops
• Exact upper bound for sorting \(R_n\) with LE
• Improved upper bound for sorting permutations by prefix transpositions
• Sorting by prefix reversals and prefix transpositions
• A note on complexity of genetic mutations
• Algorithms – ESA 2005
• Rearranging two dimensional arrays by prefix reversals
• Approximation algorithms for sorting permutations by extreme block-interchanges
• Bounding prefix transposition distance for strings and permutations
• Groupoid Action and Rearrangement Problem of Bicolor Arrays by Prefix Reversals
• (Prefix) reversal distance for (signed) strings with few blocks or small alphabets
• Girth of pancake graphs
• Pancake flipping and sorting permutations
• Uniquely pressable graphs: characterization, enumeration, and recognition

Describes a project that uses

Uses Software

• OEIS

This page was built for publication: An \((18/11)n\) upper bound for sorting by prefix reversals

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q838149)