|Title:||The weighted independent domination problem is NP-complete for chordal graphs||Authors:||Chang, Gerard-J.||Keywords:||Chordal graph;Independent domination;NP-complete;Weight||Issue Date:||2004||Start page/Pages:||351-352||Source:||Discrete Applied Mathematics 143||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.
|Appears in Collections:||數學系|
Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.