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.