MAXIMUM INDEPENDENT NUMBER FOR SERIES-PARALLEL NETWORKS

Abstract

A series-parallel network is used as a model of electric circuits. Usually, we use a series-parallel graph to represent a series-parallel network. However, there are a lot of different graph representations for a single series-parallel network. For a given graph, a subset of V(G) is called an independent set if there are no edge of G joining two vertices in S. An independent set S of G is maximum if G has no independent set S' with S' > S. The number of vertices in a maximum independent set of G is called the independent number of G and is denoted by alpha-(G). The maximum independent number alpha-(N) for a series-parallel network N is defined to be the maximum alpha(G[N]) among all possible graph representations G[N]. In this paper, we are going to present a linear time algorithm to compute alpha(N) for any series-parallel network N.