• DocumentCode
    1055931
  • Title

    Parallel dynamic programming

  • Author

    Huang, Shou-Hsuan Stephen ; Liu, Hongfei ; Viswanathan, Venkatraman

  • Author_Institution
    Dept. of Comput. Sci., Houston Univ., TX, USA
  • Volume
    5
  • Issue
    3
  • fYear
    1994
  • fDate
    3/1/1994 12:00:00 AM
  • Firstpage
    326
  • Lastpage
    328
  • Abstract
    Recurrence formulations for various problems, such as finding an optimal order of matrix multiplication, finding an optimal binary search tree, and optimal triangulation of polygons, assume a similar form. A. Gibbons and W. Rytter (1988) gave a CREW PRAM algorithm to solve such dynamic programming problems. The algorithm uses O(n6/log n) processors and runs in O(log2 n) time. In this article, a modified algorithm is presented that reduces the processor requirement to O(n6/log 5n) while maintaining the same time complexity of O(log2 n)
  • Keywords
    computational complexity; dynamic programming; parallel algorithms; CREW PRAM algorithm; matrix multiplication; optimal binary search tree; optimal triangulation of polygons; parallel dynamic programming; time complexity; Binary search trees; Computer architecture; Concurrent computing; Conferences; Dynamic programming; Histograms; Labeling; Parallel processing; Phase change random access memory; Very large scale integration;
  • fLanguage
    English
  • Journal_Title
    Parallel and Distributed Systems, IEEE Transactions on
  • Publisher
    ieee
  • ISSN
    1045-9219
  • Type

    jour

  • DOI
    10.1109/71.277784
  • Filename
    277784
    • Link To Document
    https://search.isc.ac/dl/search/defaultta.aspx?DTC=49&DC=1055931