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

Maximum and Minimum Matchings for

Series-Parallel Networks

**Shih-Yih Wang and Lih-Hsing Hsu**

National Chiao Tung University

Hsinchu, Taiwan 300, R.O.C.

Series-parallel networks are often used as models for electric circuits. We use series-parallel graphs to represent series-parallel networks. Since there are many different graph representations for a series-parallel network, we are interested in studying maximum matching in different graph representations of a single network. The number of edges in a maximum matching of *G* is called the edge independence number of G and is denoted by £](*G*). For a network *N*, the maximum matching number, £](*N*), is defined to be max{£] (*G*[*N*])|[*N*] is a graph representation for *N*}, and the minimum matching number, £]*(*N*), is defined to be min{(*G*[*N*])|[*N*] is a graph representation for *N*}. Since there exist some networks with £] (*N*) - £]*(*N*) ¡Ù *k* for any positive integer *k*, computations of £](*N*) and £]*(*N*) become significant. In this paper, we present linear time algorithms to compute £](*N*) and £]*(*N*) for any series-parallel network *N*.

Keywords: series-parallel networks, matching

Received September 23, 1994; revised August 3, 1995.

Communicated by Wen-Lien Hsu.
^{*}This work was supported in part by the National Science Council of the Republic of China under contract NSC83-0208-M009-034.