Edit distance with block deletions
type: Item
instance of: scholarly article
title: Edit distance with block deletions
zbMATH Open document ID: 1461.68087
author: Dana Shapira
author: James A. Storer
published in: Algorithms
publication date: 2019-03-26T00:00:00Z
review text: Summary: Several variants of the edit distance problem with block deletions are considered. Polynomial time optimal algorithms are presented for the edit distance with block deletions allowing character insertions and character moves, but without block moves. We show that the edit distance with block moves and block deletions is NP-complete (Nondeterministic Polynomial time problems in which any given solution to such problem can be verified in polynomial time, and any NP problem can be converted into it in polynomial time), and that it can be reduced to the problem of non-recursive block moves and block deletions within a constant factor.
Mathematics Subject Classification ID: 68Q17
Mathematics Subject Classification ID: 68U15
Mathematics Subject Classification ID: 68W25
Mathematics Subject Classification ID: 68W32
zbMATH DE Number: 7042097
zbMATH Keywords: approximation algorithms
zbMATH Keywords: text processing
zbMATH Keywords: NP-completeness
zbMATH Keywords: edit distance
zbMATH Keywords: dynamic programming
zbMATH Keywords: block operations
MaRDI profile type: Publication
full work available at URL: https://doi.org/10.3390/a4010040
OpenAlex ID: W1988010239
cites work: Algorithms on Strings, Trees and Sequences
cites work: A faster algorithm computing string edit distances
cites work: A Subquadratic Sequence Alignment Algorithm for Unrestricted Scoring Matrices
cites work: Edit distance with move operations
cites work: Algorithms for approximate string matching
cites work: Efficient algorithms for the block edit problems
cites work: Approximate nearest neighbors and sequence comparison with block operations
cites work: Q4737706
cites work: The string edit distance matching problem with moves
cites work: Q4952617
cites work: FST TCS 2003: Foundations of Software Technology and Theoretical Computer Science
cites work: Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques
cites work: The greedy algorithm for edit distance with moves
cites work: Sorting by Transpositions
cites work: Block edit models for approximate string matching
cites work: Polynomial-time algorithm for computing translocation distance between genomes
cites work: Q5390005
DOI: 10.3390/A4010040
Recommended article: Q5009593
Recommended article: Q4737692
Recommended article: Edit distance with move operations
Recommended article: String Processing and Information Retrieval
Recommended article: Edit distance and its computation
Recommended article: Block elimination distance
Recommended article: Edit Distance with Duplications and Contractions Revisited
description: scientific article; zbMATH DE number 7042097