Search
 
loader loading subjects...
cover
The Weighted Independent Domination Problem in Series-Parallel Graphs
Shun-Chieh Chang, Jia-Jie Liu, Yue-Li Wang
77 - 84
10.3233/978-1-61499-484-8-77
Frontiers in Artificial Intelligence and Applications
Volume 274: Intelligent Systems and Applications
Abstract

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.

$35.00 / €27.50 / £22.00
Add PDF to cart