Efficient computations of \(\ell _1\) and \(\ell _{\infty }\) rearrangement distances

DOI10.1016/j.tcs.2009.07.019zbMath1186.68142OpenAlexW2090066232MaRDI QIDQ732031

Amihood Amir, Piotr Indyk, Yonatan Aumann, Ely Porat, Avivit Levy

Publication date: 9 October 2009

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

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

zbMATH Keywords

pattern matchingapproximate string matchingrearrangement distances

Mathematics Subject Classification ID

Searching and sorting (68P10)

Related Items (5)

Order-preserving matching ⋮ A Simple Algorithm for Approximating the Text-To-Pattern Hamming Distance ⋮ Approximate string matching with stuck address bits ⋮ Unnamed Item ⋮ Order-preserving pattern matching indeterminate strings

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Approximate pattern matching with the \(L_1\), \(L_2\) and \(L_\infty\) metrics
• Sorting permutations by block-interchanges
• Efficient string matching with k mismatches
• Fast algorithms for approximately counting mismatches
• Approximate String Matching with Address Bit Errors
• Dictionary matching and indexing with errors and don't cares
• Pattern matching with address errors
• Generalized String Matching
• An Extension of the String-to-String Correction Problem
• Sorting by Transpositions
• Faster algorithms for string matching with k mismatches
• Automata, Languages and Programming
• On the Cost of Interchange Rearrangement in Strings

This page was built for publication: Efficient computations of \(\ell _1\) and \(\ell _{\infty }\) rearrangement distances