An optimal sublinear time parallel algorithm for some dynamic programming problems

DOI10.1016/0020-0190(94)90136-8MaRDI QIDQ1336746zbMATH OpenOpenAlexFDO

Authors Lawrence L. Larmore, Wojciech Rytter

Publication date 24 July 1995

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

Full work available at URL https://doi.org/10.1016/0020-0190(94)90136-8

zbMATH Keywords

optimal parallel computations

Mathematics Subject Classification ID

Parallel numerical computation (65Y05) Analysis of algorithms and problem complexity (68Q25) Dynamic programming (90C39) Abstract computational complexity for mathematical programming problems (90C60) Distributed algorithms (68W15)

Recommendations

• Parallel algorithms for dynamic programming recurrences with more than \(O(1)\) dependency
• scientific article; zbMATH DE number 3978860
• Efficient sublinear time parallel algorithms for dynamic programming and context-free recognition
• On efficient parallel computations for some dynamic programming problems
• Systolic algorithms for the dynamic programming problem

Cites work

• scientific article; zbMATH DE number 43583 (Why is no real title available?)
• scientific article; zbMATH DE number 52889 (Why is no real title available?)
• scientific article; zbMATH DE number 3511563 (Why is no real title available?)
• A sublinear parallel algorithm for some dynamic programming problems
• Efficient sublinear time parallel algorithms for dynamic programming and context-free recognition
• On efficient parallel computations for some dynamic programming problems
• Parallel algorithms for dynamic programming recurrences with more than \(O(1)\) dependency
• Speed of Recognition of Context-Free Languages by Array Automata

Cited in

(6)

• Design of algorithms for spatial-time reduction complexity of dynamic programming
• Efficient sublinear time parallel algorithms for dynamic programming and context-free recognition
• On efficient parallel computations for some dynamic programming problems
• Almost optimal sublinear time parallel recognition algorithms for three subclasses of context free languages
• A mixed forward-backward dynamic programming method using parallel computation
• Parallel algorithms for dynamic programming recurrences with more than \(O(1)\) dependency

This page was built for publication: An optimal sublinear time parallel algorithm for some dynamic programming problems

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1336746)