The greedy algorithm for edit distance with moves

DOI10.1016/j.ipl.2005.08.010zbMath1184.68639OpenAlexW2030016852MaRDI QIDQ1045883

Nira Shafrir, Haim Kaplan

Publication date: 18 December 2009

Published in: Information Processing Letters (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.ipl.2005.08.010

zbMATH Keywords

greedy algorithmanalysis of algorithmsstring matchingapproximation algorithmsedit distance with moves

Mathematics Subject Classification ID

Analysis of algorithms (68W40) Approximation algorithms (68W25)

Related Items (9)

Mathematical programming strategies for solving the minimum common string partition problem ⋮ Minimum common string partition revisited ⋮ Edit distance with block deletions ⋮ Filling Scaffolds with Gene Repetitions: Maximizing the Number of Adjacencies ⋮ Quick Greedy Computation for Minimum Common String Partitions ⋮ Efficient algorithms for the block edit problems ⋮ Quick greedy computation for minimum common string partition ⋮ Computational performance evaluation of two integer linear programming models for the minimum common string partition problem ⋮ Unnamed Item

Cites Work

• Unnamed Item
• Unnamed Item
• Block edit models for approximate string matching
• Approximate nearest neighbors and sequence comparison with block operations
• Algorithms on Strings, Trees and Sequences
• Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques
• Algorithms and Computation

This page was built for publication: The greedy algorithm for edit distance with moves