Dynamic edit distance table under a general weighted cost function

DOI10.1016/J.JDA.2015.05.007MaRDI QIDQ491146zbMATH OpenOpenAlexFDO

Authors Heikki Hyyrö, Kazuyuki Narisawa, Shunsuke Inenaga

Publication date 24 August 2015

Published in Journal of Discrete Algorithms (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/j.jda.2015.05.007

zbMATH Keywords

dynamic programmingedit distanceincremental string comparisongeneral cost functions

Mathematics Subject Classification ID

Algorithms on strings (68W32)

Recommendations

• A dynamic edit distance table
• scientific article; zbMATH DE number 1615270
• Dynamic RLE-compressed edit distance tables under general weighted cost functions
• scientific article; zbMATH DE number 3845091
• Compacting a dynamic edit distance table by RLE compression

Cites work

• A dynamic edit distance table
• A faster algorithm computing string edit distances
• A linear space algorithm for computing maximal common subsequences
• Algorithms on Strings
• All Highest Scoring Paths in Weighted Grid Graphs and Their Application to Finding All Approximate Repeats in Strings
• An almost quadratic time algorithm for sparse spliced alignment
• Dynamic edit distance table under a general weighted cost function
• Incremental String Comparison
• Longest Common Subsequences in Permutations and Maximum Cliques in Circle Graphs
• Semi-local string comparison: algorithmic techniques and applications
• The String-to-String Correction Problem

Cited in

(11)

• scientific article; zbMATH DE number 1615270 (Why is no real title available?)
• Dynamic edit distance table under a general weighted cost function
• Computing longest common square subsequences
• scientific article; zbMATH DE number 2052917 (Why is no real title available?)
• \(k\)-approximate quasiperiodicity under Hamming and edit distance
• Edit distance with duplications and contractions revisited
• Towards Efficient Interactive Computation of Dynamic Time Warping Distance
• Dynamic and internal longest common substring
• Compacting a dynamic edit distance table by RLE compression
• A dynamic edit distance table
• Dynamic RLE-compressed edit distance tables under general weighted cost functions

This page was built for publication: Dynamic edit distance table under a general weighted cost function

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