Tight Ω(nlgn) lower bound for finding a longest increasing subsequence

DOI10.1080/00207169708804607MaRDI QIDQ4375395zbMATH OpenOpenAlexFDO

Authors Prakash V. Ramanan

Publication date 23 June 1998

Published in International Journal of Computer Mathematics (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1080/00207169708804607

zbMATH Keywords

algebraic decision tree modellongest increasing subsequence

Mathematics Subject Classification ID

Recommendations

• Fast computation of a longest increasing subsequence and application
• An algorithm for the determination of longest increasing subsequence in a sequence
• Tight conditional lower bounds for longest common increasing subsequence
• Tight conditional lower bounds for longest common increasing subsequence
• Space-efficient algorithms for longest increasing subsequence

Cites work

• scientific article; zbMATH DE number 3740740 (Why is no real title available?)
• scientific article; zbMATH DE number 3511563 (Why is no real title available?)
• On computing the length of longest increasing subsequences

Cited in

(6)

• Why is it hard to beat \(O(n^2)\) for longest common weakly increasing subsequence?
• Space-efficient algorithms for longest increasing subsequence
• Computing a longest common almost-increasing subsequence of two sequences
• Quantum meets fine-grained complexity: sublinear time quantum algorithms for string problems
• Space-efficient algorithms for longest increasing subsequence
• The longest almost-increasing subsequence

This page was built for publication: Tight Ω(nlgn) lower bound for finding a longest increasing subsequence

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