An efficient coarse-grain multicomputer algorithm for the minimum cost parenthesizing problem |
| |
Authors: | Vianney Kengne Tchendji Jean Frédéric Myoupo |
| |
Affiliation: | 1. University of Yaounde 1, Yaounde, Cameroon 2. Universit?? de Picardie-Jules Verne, 33 rue Saint Leu, 80028, Amiens, France
|
| |
Abstract: | Several problems modeled by dynamic programming have been solved using a coarse-grain multicomputer parallel model (CGM for short). These problems use either polyadic dynamic programming or monadic non-serial dynamic programming. In this paper, we address the general case: we propose a parallel algorithm in the CGM model with p processors for the Optimal String Parenthesizing Problem or Minimum Cost Parenthesizing Problem, which is a typical polyadic non-serial dynamic programming problem. The algorithm we obtain requires ?(2p)1/2? communication rounds and, at most, O(n 3/p) time-steps on p processors. This new CGM algorithm performs better than the previously most efficient solution, which uses p communication rounds. |
| |
Keywords: | |
本文献已被 SpringerLink 等数据库收录! |
|