Faster algorithms for computing longest common increasing subsequences

DOI10.1016/j.jda.2011.03.013zbMath1230.68225OpenAlexW2131441444MaRDI QIDQ655431

Kanela Kaligosi, Irit Katriel, Gerth Stølting Brodal, Martin Kuetz

Publication date: 4 January 2012

Published in: Journal of Discrete Algorithms (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.jda.2011.03.013

zbMATH Keywords

common subsequencesincreasing subsequencessmall alphabetsVan Emde Boas trees

Mathematics Subject Classification ID

Analysis of algorithms (68W40) Algorithms on strings (68W32)

Related Items

A linear space algorithm for computing a longest common increasing subsequence, Longest common rollercoasters, Computing the longest common almost-increasing subsequence, Computing longest (common) Lyndon subsequences, An efficient algorithm for the longest common palindromic subsequence problem, Computing longest Lyndon subsequences and longest common Lyndon subsequences, The longest commonly positioned increasing subsequences problem, An efficient algorithm for enumerating longest common increasing subsequences, Why is it hard to beat \(O(n^2)\) for longest common weakly increasing subsequence?, An \(A^\ast\) search algorithm for the constrained longest common subsequence problem, A Faster Subquadratic Algorithm for the Longest Common Increasing Subsequence Problem, Tight conditional lower bounds for longest common increasing subsequence, Unnamed Item, Unnamed Item, A diagonal-based algorithm for the longest common increasing subsequence problem

Cites Work

• Enumerating longest increasing subsequences and patience sorting
• A fast algorithm for computing a longest common increasing subsequence
• A linear space algorithm for computing a longest common increasing subsequence
• Efficient algorithms for finding a longest common increasing subsequence
• A faster algorithm computing string edit distances
• On computing the length of longest increasing subsequences
• Log-logarithmic worst-case range queries are possible in space theta(N)
• Priority Search Trees
• A linear space algorithm for computing maximal common subsequences
• A fast algorithm for computing longest common subsequences
• Design and implementation of an efficient priority queue
• Longest increasing subsequences: from patience sorting to the Baik-Deift-Johansson theorem
• The String-to-String Correction Problem