Finding nucleolus of flow game
Article
Article Title | Finding nucleolus of flow game |
---|---|
ERA Journal ID | 19423 |
Article Category | Article |
Authors | Deng, Xiaotie (Author), Fang, Qizhi (Author) and Sun, Xiaoxun (Author) |
Journal Title | Journal of Combinatorial Optimization |
Journal Citation | 18 (1), pp. 64-86 |
Number of Pages | 23 |
Year | 2009 |
Place of Publication | New York, NY. USA |
ISSN | 1382-6905 |
1573-2886 | |
Digital Object Identifier (DOI) | https://doi.org/10.1007/s10878-008-9138-0 |
Web Address (URL) | http://www.springerlink.com/content/561811276p017530/fulltext.pdf |
Abstract | We study the algorithmic issues of finding the nucleolus of a flow game. The flow game is a cooperative game defined on a network D=(V,E; ω). The player set is E and the value of a coalition S ⊆ E is defined as the value of a maximum flow from source to sink in the subnetwork induced by S. We show that the nucleolus of the flow game defined on a simple network (ω(e)=1 for each e ∈ E) can be computed in polynomial time by a linear program duality approach, settling a twenty-three years old conjecture by Kalai and Zemel. In contrast, we prove that both the computation and the recognition of the nucleolus are N℘-hard for flow games with general capacity. |
Keywords | efficient algorithm; flow game; linear program duality; N℘-hard; nucleolus; maximum flows |
ANZSRC Field of Research 2020 | 460609. Networking and communications |
490101. Approximation theory and asymptotic methods | |
461399. Theory of computation not elsewhere classified | |
Public Notes | Files associated with this item cannot be displayed due to copyright restrictions. |
Byline Affiliations | City University of Hong Kong, China |
Ocean University of China, China | |
Department of Mathematics and Computing | |
Institution of Origin | University of Southern Queensland |
https://research.usq.edu.au/item/q10zy/finding-nucleolus-of-flow-game
1801
total views7
total downloads1
views this month0
downloads this month