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

DOI10.1016/J.TCS.2008.04.045zbMATH Open1191.68219DBLPjournals/tcs/ChitturiFMMSSV09OpenAlexW1968115349WikidataQ56287378 ScholiaQ56287378MaRDI QIDQ838149FDOQ838149

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

Recommendations

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

zbMATH Keywords

permutationsupper boundspancake problempancake networksorting by prefix reversals

Mathematics Subject Classification ID

Searching and sorting (68P10)

Cites Work

• Title not available (Why is that?)
• 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
• Presentations of Coxeter groups of type \(A, B\), and \(D\) using prefix-reversal generators
• A quadratic lower bound for topswops
• Some relations on prefix reversal generators of the symmetric and hyperoctahedral group
• Sorting permutations and binary strings by length-weighted rearrangements
• 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
• Algorithms – ESA 2005
• Sorting by prefix reversals and prefix transpositions
• A note on complexity of genetic mutations
• Rearranging two dimensional arrays by prefix reversals
• Groupoid Action and Rearrangement Problem of Bicolor Arrays by Prefix Reversals
• Approximation algorithms for sorting permutations by extreme block-interchanges
• Bounding prefix transposition distance for strings and permutations
• (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

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)