An \((18/11)n\) upper bound for sorting by prefix reversals
From MaRDI portal
Publication:838149
DOI10.1016/j.tcs.2008.04.045zbMath1191.68219OpenAlexW1968115349WikidataQ56287378 ScholiaQ56287378MaRDI QIDQ838149
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
Related Items (22)
The spectral gap of graphs arising from substring reversals ⋮ A NOTE ON COMPLEXITY OF GENETIC MUTATIONS ⋮ Groupoid Action and Rearrangement Problem of Bicolor Arrays by Prefix Reversals ⋮ (Prefix) reversal distance for (signed) strings with few blocks or small alphabets ⋮ Improved upper bound for sorting permutations by prefix transpositions ⋮ An Algorithm to Enumerate Grid Signed Permutation Classes ⋮ A quadratic lower bound for topswops ⋮ Physical zero-knowledge proof protocol for Topswops ⋮ Successor rules for flipping pancakes and burnt pancakes ⋮ On average and highest number of flips in pancake sorting ⋮ Girth of pancake graphs ⋮ Sorting by prefix reversals and prefix transpositions ⋮ Pancake flipping is hard ⋮ Approximation algorithms for sorting permutations by extreme block-interchanges ⋮ Sorting permutations and binary strings by length-weighted rearrangements ⋮ Uniquely pressable graphs: characterization, enumeration, and recognition ⋮ Cycles in the burnt pancake graph ⋮ UPPER BOUNDS FOR SORTING PERMUTATIONS WITH A TRANSPOSITION TREE ⋮ Some relations on prefix reversal generators of the symmetric and hyperoctahedral group ⋮ Exact upper bound for sorting Rn with LE ⋮ An Audit Tool for Genome Rearrangement Algorithms ⋮ Bounding prefix transposition distance for strings and permutations
Uses Software
Cites Work
This page was built for publication: An \((18/11)n\) upper bound for sorting by prefix reversals
