[Previous] [1] [2] [3] [4] [5] [6] [7] [8] [9] [10]

Journal of Inforamtion Science and Engineering, Vol.13 No.4, pp.665-680 (December 1997)
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.

Keywords: series-parallel networks, tree contraction, independent number

Received May 21, 1996; revised January 30, 1997.
Communicated by Shing-Tsaan Huang.
* This work was supported by the National Science Council, Republic of China, under contract NSC83-0208-M009-034.