A work-optimal CGM algorithm for the LIS problem
Garcia Thierry, Jean‐Frédéric Myoupo, Semé David · 2001
This paper presents a work-optimal CGM algorithm that solves the Longest Increasing Subsequence Problem. It can be implemented in the CGM with P processors in O(N2 ÷P) time and O(P) communication steps. It is the first CGM algorithm for this problem and it is work-optimal since the sequential algorithm has a complexity of O(N2).