Efficient algorithms for finding a longest common increasing subsequence

DOI10.1007/S10878-006-9031-7MaRDI QIDQ996830zbMATH OpenOpenAlexFDO

Authors Wun-Tat Chan, Yong Zhang, Stanley P. Y. Fung, Deshi Ye, Hong Zhu

Publication date 19 July 2007

Published in Journal of Combinatorial Optimization (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/s10878-006-9031-7

zbMATH Keywords

Design and analysis of algorithmsLongest common increasing subsequence

Mathematics Subject Classification ID

Nonnumerical algorithms (68W05) Analysis of algorithms (68W40) Protein sequences, DNA sequences (92D20)

Recommendations

• Algorithms and Computation
• Faster algorithms for computing longest common increasing subsequences
• Faster Algorithms for Computing Longest Common Increasing Subsequences
• A diagonal-based algorithm for the longest common increasing subsequence problem
• A fast algorithm for computing a longest common increasing subsequence

Cites work

• A fast algorithm for computing a longest common increasing subsequence
• A fast algorithm for computing longest common subsequences
• A faster algorithm computing string edit distances
• Adding range restriction capability to dynamic data structures
• Enumerating longest increasing subsequences and patience sorting
• Faster Algorithms for Computing Longest Common Increasing Subsequences
• scientific article; zbMATH DE number 3473265 (Why is no real title available?)
• Longest Increasing and Decreasing Subsequences
• The Complexity of Some Problems on Subsequences and Supersequences

Cited in

(21)

• An algorithm for the determination of longest increasing subsequence in a sequence
• The longest commonly positioned increasing subsequences problem
• Why is it hard to beat \(O(n^2)\) for longest common weakly increasing subsequence?
• Finding the longest common sub-pattern in sequences of temporal intervals
• A linear algorithm for 3-letter longest common weakly increasing subsequence
• Fast computation of a longest increasing subsequence and application
• Longest common rollercoasters
• Efficient algorithms for the longest common subsequence in \(k\)-length substrings
• Tight conditional lower bounds for longest common increasing subsequence
• A diagonal-based algorithm for the longest common increasing subsequence problem
• Efficient algorithms for finding interleaving relationship between sequences
• An efficient algorithm for enumerating longest common increasing subsequences
• scientific article; zbMATH DE number 2088088 (Why is no real title available?)
• Sketching, streaming, and fine-grained complexity of (weighted) LCS
• Tight conditional lower bounds for longest common increasing subsequence
• Faster Algorithms for Computing Longest Common Increasing Subsequences
• Algorithms and Computation
• Simon's congruence pattern matching
• Faster algorithms for computing longest common increasing subsequences
• The merged longest common increasing subsequence problem
• A fast algorithm for computing a longest common increasing subsequence

Describes a project that uses

Uses Software

• MUMMER

This page was built for publication: Efficient algorithms for finding a longest common increasing subsequence

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