Total balancedness condition for Steiner tree games

CSpace

	Total balancedness condition for Steiner tree games
	Fang, QZ ; Cai, MC ; Deng, XT
	2003-05-01
发表期刊	DISCRETE APPLIED MATHEMATICS
ISSN	0166-218X
卷号	127 期号:3 页码:555-563
摘要	In Steiner tree game associated with a graph G = (V,E), players consist of a subset N subset of or equal to V of nodes. The characteristic function value of a subset S subset of or equal to N of the players is the minimum weight of a Steiner tree that spans S. We show that it is NP-hard to determine whether a Steiner tree game is totally balanced, i.e., cores for all its subgames are non-empty. In addition, the NP-hardness result is also proven for deciding whether the core is non-empty, or whether an imputation is a member of the core. (C) 2002 Elsevier Science B.V. All rights reserved.
关键词	cooperative game Steiner tree core total balancedness NP-hard
语种	英语
WOS研究方向	Mathematics
WOS类目	Mathematics, Applied
WOS记录号	WOS:000182966600012
出版者	ELSEVIER SCIENCE BV
引用统计
文献类型	期刊论文
条目标识符	http://ir.amss.ac.cn/handle/2S8OKBNM/18963
专题	中国科学院数学与系统科学研究院
通讯作者	Fang, QZ
作者单位	1.Ocean Univ Qingdao, Dept Math, Qingdao 266003, Peoples R China 2.Chinese Acad Sci, Inst Syst Sci, Beijing 100080, Peoples R China 3.City Univ Hong Kong, Dept Comp Sci, Hong Kong, Hong Kong, Peoples R China
推荐引用方式 GB/T 7714	Fang, QZ,Cai, MC,Deng, XT. Total balancedness condition for Steiner tree games[J]. DISCRETE APPLIED MATHEMATICS,2003,127(3):555-563.
APA	Fang, QZ,Cai, MC,&Deng, XT.(2003).Total balancedness condition for Steiner tree games.DISCRETE APPLIED MATHEMATICS,127(3),555-563.
MLA	Fang, QZ,et al."Total balancedness condition for Steiner tree games".DISCRETE APPLIED MATHEMATICS 127.3(2003):555-563.