An optimal sublinear time parallel algorithm for some dynamic programming problems

DOI10.1016/0020-0190(94)90136-8zbMath0816.90131OpenAlexW2093803005MaRDI QIDQ1336746

Wojciech Rytter, Lawrence L. Larmore

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

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

Related Items (1)

Almost optimal sublinear time parallel recognition algorithms for three subclasses of context free languages

Cites Work

• On efficient parallel computations for some dynamic programming problems
• A sublinear parallel algorithm 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
• Efficient sublinear time parallel algorithms for dynamic programming and context-free recognition
• Unnamed Item
• Unnamed Item
• Unnamed Item

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