A LINEAR-TIME ALGORITHM TO SOLVE THE WEIGHTED PERFECT DOMINATION PROBLEM IN SERIES-PARALLEL GRAPHS

In this paper, we consider the weighted perfect domination problem in series-parallel graphs. Suppose G = (V, E) is a graph in which every vertex x is-an-element-of V has a cost c(x) and every edge e is-an-element-of E has a cost c(e). The weighted perfect domination problem is to find a subset D subset-of V such that every vertex not in D is adjacent to exactly one vertex in D and its total cost c(D) = SIGMA{c(x): x is-an-element-of D} + SIGMA{c(x, y): x is-not-an-element-of D, y is-an-element-of D and (x, y) is-an-element-of E} is minimum. This problem is NP-complete for bipartite graphs and chordal graphs. In this paper, we present a linear time algorithm for the problem in series-parallel graphs.