標題: 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
顯示於類別:期刊論文