Los puntos clave no están disponibles para este artículo en este momento.
Este artículo estudia algoritmos paralelos para el problema de la subsecuencia aumentante más larga (LIS). Sea n el tamaño de la entrada y k la longitud de la LIS de la entrada. Secuencialmente, LIS es un problema simple que se puede resolver usando programación dinámica (DP) en O(n log n) trabajo. Sin embargo, paralelizar LIS es un desafío de larga data. No tenemos conocimiento de ningún algoritmo paralelo de LIS que tenga un trabajo óptimo O(n log n) y un paralelismo no trivial (es decir, Õ(k) o o(n) de alcance).
Gu et al. (Wed,) estudiaron esta pregunta.