標題: | THE K-NEIGHBOR DOMINATION PROBLEM |
作者: | HWANG, SF CHANG, GJ 應用數學系 Department of Applied Mathematics |
關鍵字: | LOCATION PROBLEM;DOMINATION;BLOCK GRAPH;LINEAR ALGORITHM;NP-COMPLETE |
公開日期: | 17-六月-1991 |
摘要: | As a model of certain location problem, we consider the following domination problem. The k-neighbor domination problem is to select a minimum cardinality vertex set D of a graph G = (V, E) such that every vertex x not in D is adjacent to at least k vertices in D. This paper presents a linear algorithm to solve the problem for block graphs. For any fixed k, we also prove that the k-neighbor domination problem is NP-complete for some classes of graphs. |
URI: | http://hdl.handle.net/11536/14274 |
ISSN: | 0377-2217 |
期刊: | EUROPEAN JOURNAL OF OPERATIONAL RESEARCH |
Volume: | 52 |
Issue: | 3 |
起始頁: | 373 |
結束頁: | 377 |
顯示於類別: | 期刊論文 |