Prefix Reversals on Binary and Ternary Strings

DOI10.1137/060664252zbMath1154.68096arXivmath/0602456OpenAlexW2139138065WikidataQ56287388 ScholiaQ56287388MaRDI QIDQ3519196

Judith Keijsper, John Tromp, Steven Kelk, Leo van Iersel, Leen Stougie, Cor A. J. Hurkens

Publication date: 13 August 2008

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

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

zbMATH Keywords

algorithmssortingstringsgenome comparisonprefix reversalspancake flipping

Mathematics Subject Classification ID

Searching and sorting (68P10) Combinatorics on words (68R15) Protein sequences, DNA sequences (92D20) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17)

Related Items (10)

A NOTE ON COMPLEXITY OF GENETIC MUTATIONS ⋮ (Prefix) reversal distance for (signed) strings with few blocks or small alphabets ⋮ Prefix and suffix reversals on strings ⋮ Infinite families of 2-isometric and not 3-isometric binary words ⋮ Prefix and Suffix Reversals on Strings ⋮ Solution to a conjecture on words that are bad and 2-isometric ⋮ Prefix and suffix transreversals on binary and ternary strings ⋮ UPPER BOUNDS FOR SORTING PERMUTATIONS WITH A TRANSPOSITION TREE ⋮ The index of a binary word ⋮ Bounding prefix transposition distance for strings and permutations

This page was built for publication: Prefix Reversals on Binary and Ternary Strings