A linear space algorithm for computing a longest common increasing subsequence

DOI10.1016/j.ipl.2006.05.005zbMath1186.68589OpenAlexW1983269319MaRDI 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

algorithmslongest common subsequencelongest increasing subsequence

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Algorithms on strings (68W32)

Related Items

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

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