Fast computation of a longest increasing subsequence and application

DOI10.1016/j.ic.2010.04.003zbMath1214.68479OpenAlexW2009853785WikidataQ61677901 ScholiaQ61677901MaRDI QIDQ1959440

Maxime Crochemore, Ely Porat

Publication date: 7 October 2010

Published in: Information and Computation (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.ic.2010.04.003

zbMATH Keywords

dynamic programmingdata structurespriority queuelongest common subsequencelongest increasing subsequencedesign and analysis of algorithms

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Analysis of algorithms (68W40) Dynamic programming (90C39) Data structures (68P05)

Related Items

A faster reduction of the dynamic time warping distance to the longest increasing subsequence length ⋮ Space-Efficient Algorithms for Longest Increasing Subsequence ⋮ Computing a longest common subsequence that is almost increasing on sequences having no repeated elements ⋮ Subsequences in bounded ranges: matching and analysis problems ⋮ The longest commonly positioned increasing subsequences problem ⋮ Near-optimal algorithm to count occurrences of subsequences of a given length ⋮ A divide and conquer approach and a work-optimal parallel algorithm for the LIS problem ⋮ Rollercoasters and Caterpillars ⋮ Space-efficient algorithms for longest increasing subsequence ⋮ Improvised divide and conquer approach for the LIS problem ⋮ Tight conditional lower bounds for longest common increasing subsequence ⋮ Unnamed Item ⋮ Longest increasing subsequence under persistent comparison errors ⋮ Unnamed Item ⋮ A diagonal-based algorithm for the longest common increasing subsequence problem ⋮ Rollercoasters: Long Sequences without Short Runs ⋮ On-line scheduling with monotone subsequence constraints ⋮ Fast and longest rollercoasters

Uses Software

• MUMMER

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Enumerating longest increasing subsequences and patience sorting
• A fast algorithm for computing a longest common increasing subsequence
• Improving the worst-case performance of the Hunt-Szymanski strategy for the longest common subsequence of two strings
• A faster algorithm computing string edit distances
• On computing the length of longest increasing subsequences
• Preserving order in a forest in less than logarithmic time and linear space
• Finding longest increasing and common subsequences in streaming data
• Longest Increasing and Decreasing Subsequences
• A fast algorithm for computing longest common subsequences
• Design and implementation of an efficient priority queue
• Algorithms on Strings, Trees and Sequences
• On the distribution of the length of the longest increasing subsequence of random permutations
• A Subquadratic Sequence Alignment Algorithm for Unrestricted Scoring Matrices
• Deterministic sorting in O(nloglogn) time and linear space
• A New Efficient Algorithm for Computing the Longest Common Subsequence
• Algorithms on Strings

This page was built for publication: Fast computation of a longest increasing subsequence and application