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

Journal of Inforamtion Science and Engineering, Vol.12 No.1, pp.127-142 (March 1996)
Maximum and Minimum Matchings for
Series-Parallel Networks*

Shih-Yih Wang and Lih-Hsing Hsu
Department of Computer and Information Science
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.