Bounding prefix transposition distance for strings and permutations
From MaRDI portal
Publication:764373
DOI10.1016/j.tcs.2011.11.018zbMath1253.68145MaRDI 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
68R15: Combinatorics on words
68Q17: Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.)
Related Items
UPPER BOUNDS FOR SORTING PERMUTATIONS WITH A TRANSPOSITION TREE, A new upper bound for sorting permutations with prefix transpositions, Sorting by prefix reversals and prefix transpositions, Hamiltonian cycles in unitary prefix transposition rearrangement graphs, Tighter upper bound for sorting permutations with prefix transpositions, Sorting permutations and binary strings by length-weighted rearrangements, Bounding prefix transposition distance for strings and permutations, Sorting permutations with transpositions in \(O(n^3)\) amortized time, Improved upper bound for sorting permutations by prefix transpositions, An Audit Tool for Genome Rearrangement Algorithms, Sorting by Transpositions Is Difficult
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
