JISE


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


Journal of Information Science and Engineering, Vol. 12 No. 1, pp. 127-142


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

  Retrieve PDF document (JISE_199601_06.pdf)