A recurrence template for several parameters in series–parallel graphs

AbstractWe present a single set of recurrence parameters and a single set of recurrence relations which can be used to provide a linear algorithm for evaluating a wide class of graph theoretic parameters for series–parallel graphs. The set of recurrences presented here is no larger than has been necessary in solving any one of the parameters. Problems that can be solved using our template of recurrence relations include those involving the concepts of domination, packing, redundance, and independence