scientific article; zbMATH DE number 4053031

MaRDI QIDQ3789080zbMATH OpenFDO

Authors Danny Dolev, Joseph (Yossi) Gil

Publication date 1988

zbMATH Keywords

acyclic directed graphBoolean matrix multiplicationCRCW-PRAMedit distancelattice graphlongest common subsequencemaximal path lengthstring editing

Mathematics Subject Classification ID

Searching and sorting (68P10) Analysis of algorithms and problem complexity (68Q25) Graph theory (including graph drawing) in computer science (68R10) Problem solving in the context of artificial intelligence (heuristics, search strategies, etc.) (68T20)

Recommendations

• Efficient Parallel Algorithms for String Editing and Related Problems
• scientific article; zbMATH DE number 3845091
• How hard is computing the edit distance?
• An \(O(ND)\) difference algorithm and its variations
• String editing under a combination of constraints

Cited in

(8)

• A lower bound for the edit-distance problem under an arbitrary cost function
• On efficient parallel computations of costs of paths on a grid graph
• Edit distance with duplications and contractions revisited
• Efficient Parallel Algorithms for String Editing and Related Problems
• scientific article; zbMATH DE number 1516705 (Why is no real title available?)
• scientific article; zbMATH DE number 1773073 (Why is no real title available?)
• A space-efficient alphabet-independent Four-Russians' lookup table and a multithreaded Four-Russians' edit distance algorithm
• Massively parallel approximation algorithms for edit distance and longest common subsequence

This page was built for publication:

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