A fast algorithm for computing a longest common increasing subsequence

DOI10.1016/j.ipl.2004.10.014zbMath1173.68839OpenAlexW2152064395MaRDI QIDQ835045

Chien-Pin Huang, I-Hsuan Yang, Kun-Mao Chao

Publication date: 27 August 2009

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

Full work available at URL: http://ntur.lib.ntu.edu.tw//handle/246246/154520

zbMATH Keywords

algorithmscomputational biologylongest common subsequencelongest increasing subsequence

Mathematics Subject Classification ID

Nonnumerical algorithms (68W05)

Related Items (24)

A linear space algorithm for computing a longest common increasing subsequence ⋮ Efficient algorithms for finding interleaving relationship between sequences ⋮ Longest common rollercoasters ⋮ Computing the longest common almost-increasing subsequence ⋮ An efficient algorithm for the longest common palindromic subsequence problem ⋮ Computing a longest common subsequence that is almost increasing on sequences having no repeated elements ⋮ The longest commonly positioned increasing subsequences problem ⋮ An efficient algorithm for enumerating longest common increasing subsequences ⋮ Near-optimal algorithm to count occurrences of subsequences of a given length ⋮ Why is it hard to beat \(O(n^2)\) for longest common weakly increasing subsequence? ⋮ FACC: a novel finite automaton based on cloud computing for the multiple longest common subsequences search ⋮ Fast computation of a longest increasing subsequence and application ⋮ A divide and conquer approach and a work-optimal parallel algorithm for the LIS problem ⋮ Computing a longest common almost-increasing subsequence of two sequences ⋮ Faster algorithms for computing longest common increasing subsequences ⋮ A Faster Subquadratic Algorithm for the Longest Common Increasing Subsequence Problem ⋮ BIT-PARALLEL ALGORITHMS FOR THE MERGED LONGEST COMMON SUBSEQUENCE PROBLEM ⋮ Tight conditional lower bounds for longest common increasing subsequence ⋮ Unnamed Item ⋮ Longest increasing subsequence under persistent comparison errors ⋮ Efficient algorithms for finding a longest common increasing subsequence ⋮ Unnamed Item ⋮ A diagonal-based algorithm for the longest common increasing subsequence problem ⋮ Anytime algorithms for the longest common palindromic subsequence problem

Uses Software

• MUMMER

Cites Work

• Unnamed Item
• Unnamed Item
• Enumerating longest increasing subsequences and patience sorting
• A faster algorithm computing string edit distances
• On computing the length of longest increasing subsequences
• Longest Increasing and Decreasing Subsequences
• Good splitters for counting points in triangles
• A fast algorithm for computing longest common subsequences

This page was built for publication: A fast algorithm for computing a longest common increasing subsequence