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

DOI10.1080/00207169708804607zbMath0890.68055OpenAlexW2104592606MaRDI QIDQ4375395

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

longest increasing subsequencealgebraic decision tree model

Mathematics Subject Classification ID

Related Items (5)

Space-Efficient Algorithms for Longest Increasing Subsequence ⋮ Quantum meets fine-grained complexity: sublinear time quantum algorithms for string problems ⋮ Computing a longest common almost-increasing subsequence of two sequences ⋮ Space-efficient algorithms for longest increasing subsequence ⋮ The longest almost-increasing subsequence

Cites Work

• On computing the length of longest increasing subsequences
• Unnamed Item
• Unnamed Item

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