Bounding prefix transposition distance for strings and permutations

DOI10.1016/j.tcs.2011.11.018zbMath1253.68145OpenAlexW2002871031MaRDI QIDQ764373

Bhadrachalam Chitturi, Ivan Hal Sudborough

Publication date: 13 March 2012

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

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

zbMATH Keywords

complexityapproximationboundsprefix transpositions

Mathematics Subject Classification ID

Combinatorics on words (68R15) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17)

Related Items (11)

Improved upper bound for sorting permutations by prefix transpositions ⋮ Sorting by prefix reversals and prefix transpositions ⋮ Sorting permutations with transpositions in \(O(n^3)\) amortized time ⋮ Hamiltonian cycles in unitary prefix transposition rearrangement graphs ⋮ Tighter upper bound for sorting permutations with prefix transpositions ⋮ Sorting by Transpositions Is Difficult ⋮ Sorting permutations and binary strings by length-weighted rearrangements ⋮ UPPER BOUNDS FOR SORTING PERMUTATIONS WITH A TRANSPOSITION TREE ⋮ An Audit Tool for Genome Rearrangement Algorithms ⋮ Bounding prefix transposition distance for strings and permutations ⋮ A new upper bound for sorting permutations with prefix transpositions

Cites Work

• Unnamed Item
• Unnamed Item
• Bounding prefix transposition distance for strings and permutations
• An \((18/11)n\) upper bound for sorting by prefix reversals
• Bounds for sorting by prefix reversal
• Sorting by bounded block-moves
• Exact and approximation algorithms for sorting by reversals, with application to genome rearrangement
• Short proofs for cut-and-paste sorting of permutations
• A simpler and faster 1.5-approximation algorithm for sorting by transpositions
• Minimum common string partition problem: hardness and approximations
• Sorting Strings by Reversals and by Transpositions
• A NOTE ON COMPLEXITY OF GENETIC MUTATIONS
• The string edit distance matching problem with moves
• Sorting by Transpositions Is Difficult
• Adjacent Swaps on Strings
• Prefix Reversals on Binary and Ternary Strings
• Edit Distances and Factorisations of Even Permutations
• `` Strong NP-Completeness Results
• On the Diameter of the Pancake Network
• Sorting by Transpositions
• Genome Rearrangements and Sorting by Reversals
• Reversals and Transpositions Over Finite Alphabets
• Block Sorting is Hard
• Sorting a bridge hand

This page was built for publication: Bounding prefix transposition distance for strings and permutations