Improvised divide and conquer approach for the LIS problem

DOI10.1016/j.jda.2018.01.001zbMath1391.68130OpenAlexW2792575467MaRDI QIDQ1748198

Seema Rani, Dharmveer Singh Rajpoot

Publication date: 9 May 2018

Published in: Journal of Discrete Algorithms (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.jda.2018.01.001

zbMATH Keywords

divide-and-conquerlongest increasing subsequenceprincipal row of Young tableaux

Mathematics Subject Classification ID

Algorithms on strings (68W32)

Uses Software

• MUMMER

Cites Work

• Unnamed Item
• Unnamed Item
• Enumerating longest increasing subsequences and patience sorting
• The longest almost-increasing subsequence
• On the longest increasing subsequence of a circular list
• An algorithm for solving the longest increasing circular subsequence problem
• The constrained longest common subsequence problem
• On computing the length of longest increasing subsequences
• Preserving order in a forest in less than logarithmic time and linear space
• Longest increasing subsequences in sliding windows
• Fast computation of a longest increasing subsequence and application
• Longest increasing subsequences in windows based on canonical antichain partition
• A divide and conquer approach and a work-optimal parallel algorithm for the LIS problem
• Longest Increasing and Decreasing Subsequences