Calculating distances for dissimilar strings: the shortest path formulation revisited

DOI10.1016/J.EJOR.2005.09.005MaRDI QIDQ856246zbMATHOpenAlexFDO

Authors Konstantinos Spiliopoulos, Stella Sofianopoulou

Publication date 7 December 2006

Published in European Journal of Operational Research (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/j.ejor.2005.09.005

zbMATH Keywords

shortest path problemstring matchingcomputing scienceLevenshtein distancedata cleansing

Mathematics Subject Classification ID

Operations research and management science (90B99)

Recommendations

• scientific article; zbMATH DE number 7203332
• Algorithms for closest and farthest string problems via rank distance
• scientific article; zbMATH DE number 2090203
• A new distance metric on strings computable in linear time
• On the closest string via rank distance
• Approximating reversal distance for strings with bounded number of duplicates
• Mathematical Foundations of Computer Science 2005
• Finding shortest and dissimilar paths
• Two shortest path metrics on well-formed parentheses strings

Cites work

• scientific article; zbMATH DE number 1516705 (Why is no real title available?)
• scientific article; zbMATH DE number 828444 (Why is no real title available?)
• scientific article; zbMATH DE number 3240929 (Why is no real title available?)
• A Subquadratic Sequence Alignment Algorithm for Unrestricted Scoring Matrices
• A linear space algorithm for computing maximal common subsequences
• Algorithms for the Longest Common Subsequence Problem
• An O(NP) sequence comparison algorithm
• An \(O(ND)\) difference algorithm and its variations
• The String-to-String Correction Problem
• The longest common subsequence problem revisited

Cited in

(4)

• Research trends in combinatorial optimization
• scientific article; zbMATH DE number 1832301 (Why is no real title available?)
• scientific article; zbMATH DE number 1945862 (Why is no real title available?)
• scientific article; zbMATH DE number 7203332 (Why is no real title available?)

This page was built for publication: Calculating distances for dissimilar strings: the shortest path formulation revisited

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