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

Extended Tree Contraction for Some Parallel

Algorithms on Series-parallel Networks

**Jeng-Jung Wang, Shih-Yih Wang, Lih-Hsing Hsu and Ting-Yi Sung ^{#}**

National Chiao Tung University

Hsinchu, Taiwan 300, R.O.C.

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.