A linear time algorithm to solve the weighted perfect domination problem in series-parallel graphs

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