MAXIMUM INDEPENDENT, MINIMALLY REDUNDANT SETS IN SERIES-PARALLEL GRAPHS

Abstract

We introduce a new type of graph-theoretic parameter, namely, “single set, prioritized multi-property” parameters. The example described here uses independence as the priority property and redundance as the secondary property, and we consider the problem of minimizing (total) redundance for a maximum independent set S. We show that we have an Np-hard problem but that there exists a linear time algorithm to find such a set S in a series-parallel graph.