A divide and conquer approach and a work-optimal parallel algorithm for the LIS problem

DOI10.1016/j.ipl.2013.03.013zbMath1296.68187OpenAlexW2045565895MaRDI QIDQ2444738

Muhammad Rashed Alam, M. Sohel Rahman

Publication date: 11 April 2014

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

Full work available at URL: https://doi.org/10.1016/j.ipl.2013.03.013

zbMATH Keywords

parallel algorithmslongest increasing subsequencedivide and conquer

Mathematics Subject Classification ID

Parallel algorithms in computer science (68W10) Algorithms on strings (68W32)

Related Items

Improvised divide and conquer approach for the LIS problem

Uses Software

• Cilk
• Intel TBB
• MUMMER

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• A fast algorithm for computing a longest common increasing subsequence
• A faster algorithm computing string edit distances
• On computing the length of longest increasing subsequences
• Fast computation of a longest increasing subsequence and application
• Encyclopedia of Parallel Computing
• Longest Increasing and Decreasing Subsequences
• A CGM Algorithm Solving the Longest Increasing Subsequence Problem
• A fast algorithm for computing longest common subsequences
• Design and implementation of an efficient priority queue
• The String-to-String Correction Problem
• A Subquadratic Sequence Alignment Algorithm for Unrestricted Scoring Matrices