CSpace
Total balancedness condition for Steiner tree games
Fang, QZ; Cai, MC; Deng, XT
2003-05-01
Source PublicationDISCRETE APPLIED MATHEMATICS
ISSN0166-218X
Volume127Issue:3Pages:555-563
AbstractIn 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.
Keywordcooperative game Steiner tree core total balancedness NP-hard
Language英语
WOS Research AreaMathematics
WOS SubjectMathematics, Applied
WOS IDWOS:000182966600012
PublisherELSEVIER SCIENCE BV
Citation statistics
Cited Times:3[WOS]   [WOS Record]     [Related Records in WOS]
Document Type期刊论文
Identifierhttp://ir.amss.ac.cn/handle/2S8OKBNM/18963
Collection中国科学院数学与系统科学研究院
Affiliation1.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
Recommended Citation
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.
Files in This Item:
There are no files associated with this item.
Related Services
Recommend this item
Bookmark
Usage statistics
Export to Endnote
Google Scholar
Similar articles in Google Scholar
[Fang, QZ]'s Articles
[Cai, MC]'s Articles
[Deng, XT]'s Articles
Baidu academic
Similar articles in Baidu academic
[Fang, QZ]'s Articles
[Cai, MC]'s Articles
[Deng, XT]'s Articles
Bing Scholar
Similar articles in Bing Scholar
[Fang, QZ]'s Articles
[Cai, MC]'s Articles
[Deng, XT]'s Articles
Terms of Use
No data!
Social Bookmark/Share
All comments (0)
No comment.
 

Items in the repository are protected by copyright, with all rights reserved, unless otherwise indicated.