Extended Tree Contraction for Some Parallel Algorithms on Series-parallel Networks
Jeng-Jung Wang, Shih-Yih Wang, Lih-Hsing Hsu and Ting-Yi Sung# Department of Computer and Information Science National Chiao Tung University Hsinchu, Taiwan 300, R.O.C. # Institute of Information Science Academia Sinica Taipei, Taiwan 11529, R.O.C.
Series-parallel networks are used as models for electric circuits. In some applications, we need to evaluate a parameter F(N) for a series-parallel network N. It is known that every series-parallel network N corresponds to a parse-tree T(N). Usually, we may sequentially evaluate F(N) using dynamic programming techniques on T(N). If the function F is symmetric, we may apply the tree contraction technique to evaluate F(N) in parallel. Nevertheless, many functions defined on series-parallel networks are non-symmetric. A single series-parallel network N may have many different graph representations G[N] corresponding to N. Let f be any function defined on graphs. We can define another function F on series-parallel networks by setting F(N) to be the optimal value among all f(G[N]). The function F defined in this manner is not necessarily symmetric. In this paper, we apply the idea of tree contraction to compute in parallel some non-symmetric functions F on series-parallel networks.