https://scholars.lib.ntu.edu.tw/handle/123456789/30241
標題: | The weighted independent domination problem is NP-complete for chordal graphs | 作者: | Chang, Gerard-J. | 關鍵字: | Chordal graph;Independent domination;NP-complete;Weight | 公開日期: | 2004 | 起(迄)頁: | 351-352 | 來源出版物: | Discrete Applied Mathematics 143 | 摘要: | 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. |
URI: | http://ntur.lib.ntu.edu.tw//handle/246246/2006111501244128 | 其他識別: | 246246/2006111501244128 |
顯示於: | 數學系 |
在 IR 系統中的文件,除了特別指名其著作權條款之外,均受到著作權保護,並且保留所有的權利。