Longest common subsequence in sublinear space

DOI10.1016/j.ipl.2020.106084OpenAlexW3115081193MaRDI QIDQ2656347

Yota Otachi, Takashi Horiyama, Masashi Kiyomi

Publication date: 11 March 2021

Published in: Information Processing Letters (Search for Journal in Brave)

Full work available at URL: https://arxiv.org/abs/2009.08588

zbMATH Keywords

computational complexitylongest common subsequenceLevenshtein distancespace-efficient algorithm

Mathematics Subject Classification ID

Theory of computing (68Qxx)

Related Items (3)

Computing longest (common) Lyndon subsequences ⋮ Computing longest Lyndon subsequences and longest common Lyndon subsequences ⋮ Longest bordered and periodic subsequences

Cites Work

• Unnamed Item
• Relationships between nondeterministic and deterministic tape complexities
• Improved Approximation for Fréchet Distance on c-packed Curves Matching Conditional Lower Bounds
• A linear space algorithm for computing maximal common subsequences
• The String-to-String Correction Problem
• Edit Distance Cannot Be Computed in Strongly Subquadratic Time (Unless SETH is False)
• Constant-factor approximation of near-linear edit distance in near-linear time
• Constant factor approximations to edit distance on far input pairs in nearly linear time
• Reducing approximate Longest Common Subsequence to approximate Edit Distance
• Approximating LCS in Linear Time: Beating the √n Barrier
• Simulating branching programs with edit distance and friends: or: a polylog shaved is a lower bound made

This page was built for publication: Longest common subsequence in sublinear space