THE K-NEIGHBOR DOMINATION PROBLEM

Full metadata record

DC Field	Value	Language
dc.contributor.author	HWANG, SF	en_US
dc.contributor.author	CHANG, GJ	en_US
dc.date.accessioned	2014-12-08T15:20:08Z	-
dc.date.available	2014-12-08T15:20:08Z	-
dc.date.issued	1991-06-17	en_US
dc.identifier.issn	0377-2217	en_US
dc.identifier.uri	http://hdl.handle.net/11536/14274	-
dc.description.abstract	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.	en_US
dc.language.iso	en_US	en_US
dc.subject	LOCATION PROBLEM	en_US
dc.subject	DOMINATION	en_US
dc.subject	BLOCK GRAPH	en_US
dc.subject	LINEAR ALGORITHM	en_US
dc.subject	NP-COMPLETE	en_US
dc.title	THE K-NEIGHBOR DOMINATION PROBLEM	en_US
dc.type	Article	en_US
dc.identifier.journal	EUROPEAN JOURNAL OF OPERATIONAL RESEARCH	en_US
dc.citation.volume	52	en_US
dc.citation.issue	3	en_US
dc.citation.spage	373	en_US
dc.citation.epage	377	en_US
dc.contributor.department	應用數學系	zh_TW
dc.contributor.department	Department of Applied Mathematics	en_US
dc.identifier.wosnumber	WOS:A1991FX28100012	-
dc.citation.woscount	1	-
Appears in Collections:	Articles