The Weighted Independent Domination Problem in Series-Parallel Graphs
Shun‐Chieh Chang, Liu Jia-Jie, Yue-Li Wang · Frontiers in artificial intelligence and applications · 2015
A set S of vertices in a graph G=(V,E) is an independent dominating set of G if no two vertices in S are adjacent and every vertex not in S is adjacent to a vertex in S. Suppose every vertex v∈V and every edge e∈E are associated with a cost which is a real number, denoted by c(v) and c(e), respectively. The weighted independent domination problem is to find an independent dominating set D such that its total cost c(D)=Σx∈Dc(x)+Σx∉Dmin {c(x,y), for y∈D and (x,y)∈E} is minimum. In this paper, we propose a linear time algorithm for solving this problem in series-parallel graphs.