https://scholars.lib.ntu.edu.tw/handle/123456789/30241
DC 欄位 | 值 | 語言 |
---|---|---|
dc.contributor | National Taiwan University Dept Math | en |
dc.contributor.author | Chang, Gerard-J. | en |
dc.creator | Chang, Gerard-J. | en |
dc.date | 2004 | zh_TW |
dc.date.accessioned | 2006-11-15T01:00:00Z | - |
dc.date.accessioned | 2018-06-28T09:11:43Z | - |
dc.date.available | 2006-11-15T01:00:00Z | - |
dc.date.available | 2018-06-28T09:11:43Z | - |
dc.date.issued | 2004 | - |
dc.identifier | 246246/2006111501244128 | zh_TW |
dc.identifier.uri | http://ntur.lib.ntu.edu.tw//handle/246246/2006111501244128 | - |
dc.description.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. | en |
dc.format | application/pdf | en |
dc.format.extent | 161095 bytes | en |
dc.format.mimetype | application/pdf | en |
dc.language | en-US | en |
dc.language.iso | zh_TW | zh_TW |
dc.relation | Discrete Applied Mathematics 143,351-352 | en |
dc.relation.ispartof | Discrete Applied Mathematics 143 | - |
dc.source | http://www.sciencedirect.com/ | en |
dc.subject | Chordal graph | en |
dc.subject | Independent domination | en |
dc.subject | NP-complete | en |
dc.subject | Weight | en |
dc.title | The weighted independent domination problem is NP-complete for chordal graphs | en |
dc.type | journal article | en |
dc.relation.pages | 351-352 | - |
dc.identifier.uri.fulltext | http://ntur.lib.ntu.edu.tw/bitstream/246246/2006111501244128/1/4700.pdf | - |
item.openairetype | journal article | - |
item.fulltext | with fulltext | - |
item.languageiso639-1 | zh_TW | - |
item.cerifentitytype | Publications | - |
item.grantfulltext | open | - |
item.openairecristype | http://purl.org/coar/resource_type/c_6501 | - |
顯示於: | 數學系 |
在 IR 系統中的文件,除了特別指名其著作權條款之外,均受到著作權保護,並且保留所有的權利。