Parallel algorithms for dynamic programming recurrences with more than \(O(1)\) dependency

DOI10.1006/JPDC.1994.1053zbMath0820.90122OpenAlexW2059310886MaRDI QIDQ1328093

Zvi Galil, Kun Soo Park

Publication date: 14 September 1995

Published in: Journal of Parallel and Distributed Computing (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1006/jpdc.1994.1053

zbMATH Keywords

dynamic programmingparallel computationRNA problem

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Dynamic programming (90C39) Parallel numerical computation (65Y05) Distributed algorithms (68W15)

Related Items (6)

An optimal sublinear time parallel algorithm for some dynamic programming problems ⋮ An optimal parallel algorithm for computing a near-optimal order of matrix multiplications ⋮ On a sublinear time parallel construction of optimal binary search trees ⋮ An efficient parallel algorithm for scheduling interval ordered tasks ⋮ An algorithm for the sequence alignment with gap penalty problem using multiway divide-and-conquer and matrix transposition ⋮ From the theory to the tools: parallel dynamic programming

This page was built for publication: Parallel algorithms for dynamic programming recurrences with more than \(O(1)\) dependency