A linear space algorithm for computing a longest common increasing subsequence

DOI10.1016/j.ipl.2006.05.005zbMath1186.68589MaRDI QIDQ845723

Yoshifumi Sakai

Publication date: 29 January 2010

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

Full work available at URL: https://doi.org/10.1016/j.ipl.2006.05.005

zbMATH Keywords

algorithms; longest common subsequence; longest increasing subsequence

Mathematics Subject Classification ID

68Q25: Analysis of algorithms and problem complexity

68W32: Algorithms on strings

Related Items

A Faster Subquadratic Algorithm for the Longest Common Increasing Subsequence Problem, Computing a longest common subsequence that is almost increasing on sequences having no repeated elements, On the limiting law of the length of the longest common and increasing subsequences in random words, Faster algorithms for computing longest common increasing subsequences, Why is it hard to beat \(O(n^2)\) for longest common weakly increasing subsequence?, A diagonal-based algorithm for the longest common increasing subsequence problem, An efficient algorithm for enumerating longest common increasing subsequences

Uses Software

• MUMMER

Cites Work

• Enumerating longest increasing subsequences and patience sorting
• Faster algorithms for computing longest common increasing subsequences
• A fast algorithm for computing a longest common increasing subsequence
• An almost-linear time and linear space algorithm for the longest common subsequence problem
• A faster algorithm computing string edit distances
• Longest Increasing and Decreasing Subsequences
• A linear space algorithm for computing maximal common subsequences
• Algorithms and Computation