The greedy algorithm for edit distance with moves

DOI10.1016/j.ipl.2005.08.010zbMath1184.68639MaRDI 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 algorithm; analysis of algorithms; string matching; approximation algorithms; edit distance with moves

Mathematics Subject Classification ID

68W40: Analysis of algorithms

68W25: Approximation algorithms

Related Items

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

Cites Work

• 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
• Unnamed Item
• Unnamed Item