On efficient parallel computations for some dynamic programming problems

DOI10.1016/0304-3975(88)90147-8zbMath0655.90092OpenAlexW2047162848MaRDI QIDQ1109691

Wojciech Rytter

Publication date: 1988

Published in: Theoretical Computer Science (Search for Journal in Brave)

Full work available at URL: http://wrap.warwick.ac.uk/60800/7/WRAP_cs-rr-104.pdf

zbMATH Keywords

generalized parsingoptimal binary search treeoptimal order of matrix multiplicationsoptimal triangulation of polygonsparallelization of some dynamic programming algorithms

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Numerical mathematical programming methods (65K05) Dynamic programming (90C39)

Related Items (10)

Finding least-weight subsequences with fewer processors ⋮ An optimal sublinear time parallel algorithm for some dynamic programming problems ⋮ An optimal parallel algorithm for computing a near-optimal order of matrix multiplications ⋮ Systolic algorithms for the dynamic programming problem ⋮ Categories, relations and dynamic programming ⋮ Parallel recognition and ranking of context-free languages ⋮ On a sublinear time parallel construction of optimal binary search trees ⋮ Parallel tree-contraction and Fibonacci numbers ⋮ A sublinear parallel algorithm for some dynamic programming problems ⋮ Parallel algorithms for a class of graphs generated recursively

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• An introduction to parallelism in combinatorial optimization
• On the complexity of parallel parsing of general context-free languages
• Parallel time O(log n) recognition of unambiguous context-free languages
• Parallel computation and conflicts in memory access
• Fast Parallel Computation of Polynomials Using Few Processors
• Ultracomputers
• Parallel Matrix and Graph Algorithms

This page was built for publication: On efficient parallel computations for some dynamic programming problems