Exploiting pseudo-locality of interchange distance

DOI10.1016/J.IC.2025.105324MaRDI QIDQ6931990zbMATH OpenFDO

Authors Avivit Levy

Publication date 9 September 2025

Published in Information and Computation (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/J.IC.2025.105324

Mathematics Subject Classification ID

Data structures (68P05) Approximation algorithms (68W25) Algorithms on strings (68W32)

Cites work

• A simple algorithm for approximating the text-to-pattern Hamming distance
• An Extension of the String-to-String Correction Problem
• An improved data stream summary: the count-min sketch and its applications
• Approximate Hamming distance in a stream
• Approximate nearest neighbor: towards removing the curse of dimensionality
• Approximate swapped matching.
• Approximating text-to-pattern Hamming distances
• Cycle detection and correction
• Efficient Search for Approximate Nearest Neighbor in High Dimensional Spaces
• Fast algorithms for abelian periods in words and greatest common divisor queries
• Fast algorithms for approximately counting mismatches
• Faster algorithms for string matching problems: matching the convolution bound
• Faster algorithms for text-to-pattern Hamming distances
• scientific article; zbMATH DE number 3471577 (Why is no real title available?)
• scientific article; zbMATH DE number 1775450 (Why is no real title available?)
• scientific article; zbMATH DE number 2086663 (Why is no real title available?)
• scientific article; zbMATH DE number 3240929 (Why is no real title available?)
• Improved online algorithms for jumbled matching
• Interchange rearrangement: the element-cost model
• LCSk: a refined similarity measure
• On approximate jumbled pattern matching in strings
• On the cost of interchange rearrangement in strings
• Optimal approximations of the frequency moments of data streams
• Optimal data-dependent hashing for approximate near neighbors
• Overlap matching.
• Pattern matching with address errors: rearrangement distances
• Polynomial-time algorithm for computing translocation distance between genomes
• Sorting by Transpositions
• Sorting permutations by block-interchanges
• Sorting Permutations by Reversals and Eulerian Cycle Decompositions
• Storing a Sparse Table with 0 (1) Worst Case Access Time
• String rearrangement metrics: a survey
• The complexity of finding minimum-length generator sequences

This page was built for publication: Exploiting pseudo-locality of interchange distance

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