Maximum independent number for series‐parallel networks
Lih‐Hsing Hsu, Shih‐Yih Wang · Networks · 1991
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 α(G). The maximum independent number α(N) for a series‐parallel network N is defined to be the maximum α(G[N]) among all possible graph representations G[N]. In this paper, we are going to present a linear time algorithm to compute α(N) for any series‐parallel network N.