Adjacent Swaps on Strings

DOI10.1007/978-3-540-69733-6_30MaRDI QIDQ3511341zbMATH OpenOpenAlexFDO

Authors Bhadrachalam Chitturi, Hal Sudborough, Walter Voit, Xuerong Feng

Publication date 10 July 2008

Published in Lecture Notes in Computer Science (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/978-3-540-69733-6_30

Mathematics Subject Classification ID

Combinatorics in computer science (68R05) Nonnumerical algorithms (68W05)

Recommendations

• Mathematical Foundations of Computer Science 2005
• Efficient algorithms for approximate string matching with swaps
• Reversal Distance for Strings with Duplicates: Linear Time Approximation Using Hitting Set
• Pattern Matching with Swaps
• Approximating reversal distance for strings with bounded number of duplicates

Cites work

• Sorting with fixed-length reversals
• Transforming cabbage into turnip

Cited in

(6)

• Layered graphs: applications and algorithms
• Sorting on graphs by adjacent swaps using permutation groups
• A note on complexity of genetic mutations
• Upper bounds for sorting permutations with a transposition tree
• Interchange rearrangement: the element-cost model
• Bounding prefix transposition distance for strings and permutations

This page was built for publication: Adjacent Swaps on Strings

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3511341)