The weighted independent domination problem is NP-complete for chordal graphs
Resource
Discrete Applied Mathematics 143,351-352
Journal
Discrete Applied Mathematics 143
Pages
351-352
Date Issued
2004
Date
2004
Author(s)
Chang, Gerard-J.
DOI
246246/2006111501244128
Abstract
An independent dominatingset of a graph G = (V; E) 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 3nd 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.
Subjects
Chordal graph
Independent domination
NP-complete
Weight
Type
journal article
File(s)![Thumbnail Image]()
Loading...
Name
4700.pdf
Size
23.19 KB
Format
Adobe PDF
Checksum
(MD5):0aa8080843778e2d54b74811a5db48ce