The weighted independent domination problem is NP-complete for chordal graphs

被引：21

作者：

Chang, GJ ^{[1
]}

机构：

[1] Natl Taiwan Univ, Dept Math, Taipei 106, Taiwan

来源：

DISCRETE APPLIED MATHEMATICS | 2004年 / 143卷 / 1-3期

关键词：

chordal graph; independent domination; NP-complete; weight;

D O I：

10.1016/j.dam.2003.05.004

中图分类号：

O29 [应用数学];

学科分类号：

070104 ;

摘要：

An independent dominating set of a graph G = (VE) is a pairwise non-adjacent subset D of V such that every vertex not in D is adjacent to at least one vertex in D. Suppose each vertex in V is associated with a weight which is a real number. The weighted independent domination problem is to find an independent domination set of minimum total weights. This paper records an unpublished result of 20 years ago that the weighted independent domination problem is NP-complete for chordal graphs. (C) 2003 Elsevier B.V. All rights reserved.

引用

页码：351 / 352

页数：2