Finding nucleolus of flow game

Research output: Journal Publications and Reviews (RGC: 21, 22, 62)21_Publication in refereed journalpeer-review

29 Scopus Citations
View graph of relations

Author(s)

  • Xiaotie Deng
  • Qizhi Fang
  • Xiaoxun Sun

Related Research Unit(s)

Detail(s)

Original languageEnglish
Pages (from-to)64-86
Journal / PublicationJournal of Combinatorial Optimization
Volume18
Issue number1
Publication statusPublished - Jul 2009

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. © 2008 Springer Science+Business Media, LLC.

Research Area(s)

  • Efficient algorithm, Flow game, Linear program duality, N℘-hard, Nucleolus

Citation Format(s)

Finding nucleolus of flow game. / Deng, Xiaotie; Fang, Qizhi; Sun, Xiaoxun.

In: Journal of Combinatorial Optimization, Vol. 18, No. 1, 07.2009, p. 64-86.

Research output: Journal Publications and Reviews (RGC: 21, 22, 62)21_Publication in refereed journalpeer-review