Finding nucleolus of flow game

Article

Deng, Xiaotie, Fang, Qizhi and Sun, Xiaoxun. 2009. "Finding nucleolus of flow game ." Journal of Combinatorial Optimization. 18 (1), pp. 64-86. https://doi.org/10.1007/s10878-008-9138-0
Article Title

Finding nucleolus of flow game

ERA Journal ID19423
Article CategoryArticle
AuthorsDeng, Xiaotie (Author), Fang, Qizhi (Author) and Sun, Xiaoxun (Author)
Journal TitleJournal of Combinatorial Optimization
Journal Citation18 (1), pp. 64-86
Number of Pages23
Year2009
Place of PublicationNew York, NY. USA
ISSN1382-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.

Keywordsefficient algorithm; flow game; linear program duality; N℘-hard; nucleolus; maximum flows
ANZSRC Field of Research 2020460609. 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 AffiliationsCity University of Hong Kong, China
Ocean University of China, China
Department of Mathematics and Computing
Institution of OriginUniversity of Southern Queensland
Permalink -

https://research.usq.edu.au/item/q10zy/finding-nucleolus-of-flow-game

Log in to edit
  • 1807
    total views
  • 7
    total downloads
  • 3
    views this month
  • 0
    downloads this month

Export as

Related outputs

Algorithms for core stability, core largeness, exactness, and extendability of flow games
Fang, Qizhi, Fleischer, Rudolf, Li, Jian and Sun, Xiaoxun. 2007. "Algorithms for core stability, core largeness, exactness, and extendability of flow games ." Lin, G. (ed.) COCOON 2007: 13th Annual International Computing and Combinatorics Conference. Banff, Canada 16 - 19 Jul 2007 Berlin, Germany. https://doi.org/10.1007/978-3-540-73545-8_43
Satisfying privacy requirements before data anonymization
Sun, Xiaoxun, Wang, Hua, Li, Jiuyong and Zhang, Yanchun. 2012. "Satisfying privacy requirements before data anonymization ." The Computer Journal. 55 (4), pp. 422-437. https://doi.org/10.1093/comjnl/bxr028
An approximate microaggregation approach for microdata protection
Sun, Xiaoxun, Wang, Hua, Li, Jiuyong and Zhang, Yanchun. 2012. "An approximate microaggregation approach for microdata protection." Expert Systems with Applications. 39 (2), pp. 2211-2219. https://doi.org/10.1016/j.eswa.2011.04.223
On the identity anonymization of high-dimensional rating data
Sun, Xiaoxun, Wang, Hua and Zhang, Yanchun. 2012. "On the identity anonymization of high-dimensional rating data." Concurrency and Computation: Practice and Experience. 24 (10), pp. 1108-1122. https://doi.org/10.1002/cpe.1724
Multi-level delegations with trust management in access control systems
Li, Min, Sun, Xiaoxun, Wang, Hua and Zhang, Yanchun. 2012. "Multi-level delegations with trust management in access control systems." Journal of Intelligent Information Systems. 39 (3), pp. 611-626. https://doi.org/10.1007/s10844-012-0205-8
Publishing anonymous survey rating data
Sun, Xiaoxun, Wang, Hua, Li, Jiuyong and Pei, Jian. 2011. "Publishing anonymous survey rating data." Data Mining and Knowledge Discovery. 23 (3), pp. 379-406. https://doi.org/10.1007/s10618-010-0208-4
Injecting purpose and trust into data anonymisation
Sun, Xiaoxun, Wang, Hua, Li, Jiuyong and Zhang, Yanchun. 2011. "Injecting purpose and trust into data anonymisation." Computers and Security. 30 (5), pp. 332-345. https://doi.org/10.1016/j.cose.2011.05.005
Extended k-anonymity models against sensitive attribute disclosure
Sun, Xiaoxun, Sun, Lili and Wang, Hua. 2011. "Extended k-anonymity models against sensitive attribute disclosure." Computer Communications. 34 (4), pp. 526-535. https://doi.org/10.1016/j.comcom.2010.03.020
A family of enhanced (L,alpha) diversity models for privacy preserving data publishing
Sun, Xiaoxun, Li, Min and Wang, Hua. 2011. "A family of enhanced (L,alpha) diversity models for privacy preserving data publishing." Future Generation Computer Systems: the international journal of grid computing: theory, methods and applications. 27 (3), pp. 348-356. https://doi.org/10.1016/j.future.2010.07.007
Privacy aware access control with trust management in web service
Li, Min, Sun, Xiaoxun, Wang, Hua, Zhang, Yanchun and Zhang, Ji. 2011. "Privacy aware access control with trust management in web service." World Wide Web. 14 (4), pp. 407-430. https://doi.org/10.1007/s11280-011-0114-8
Privacy preserving data sharing in data mining environment
Sun, Xiaoxun. 2010. Privacy preserving data sharing in data mining environment. PhD Thesis Doctor of Philosophy. University of Southern Queensland.
Achieving p-sensitive k-anonymity via anatomy
Sun, Xiaoxun, Wang, Hua, Li, Jiuyong and Ross, David. 2009. "Achieving p-sensitive k-anonymity via anatomy." ICEBE 2009: IEEE International Conference on e-Business Engineering . Macau, China 21 - 23 Oct 2009 United States. https://doi.org/10.1109/ICEBE.2009.34
Extended K-anonymity models against attribute disclosure
Sun, Xiaoxun, Wang, Hua and Sun, Lili. 2009. "Extended K-anonymity models against attribute disclosure." NSS 2009: 3rd International Conference on Network and System Security. Gold Coast, Australia 19 - 21 Oct 2009 United States. https://doi.org/10.1109/NSS.2009.23
L-diversity based dynamic update for large time-evolving microdata
Sun, Xiaoxun, Wang, Hua and Li, Jiuyong. 2008. "L-diversity based dynamic update for large time-evolving microdata." Wobcke, Wayne and Zhang, Mengjie (ed.) AI 2008: 21st Australasian Joint Conference on Artificial Intelligence: Advances in Artificial Intelligence . Auckland, New Zealand 01 - 05 Dec 2008 Germany. Springer. https://doi.org/10.1007/978-3-540-89378-3_47
Optimal privacy-aware path in hippocratic databases
Li, Min, Sun, Xiaoxun, Wang, Hua and Zhang, Yanchun. 2009. "Optimal privacy-aware path in hippocratic databases." Zhou, X. (ed.) DASFAA 2009: 14th International Conference on Database Systems for Advanced Applications. Brisbane, Australia 21 - 23 Apr 2009 Germany. Springer. https://doi.org/10.1007/978-3-642-00887-0_39
(p+, α)-sensitive k-anonymity: a new enhanced privacy protection model
Sun, Xiaoxun, Wang, Hua, Truta, Traian Marius, Li, Jiuyong and Li, Ping. 2008. "(p+, α)-sensitive k-anonymity: a new enhanced privacy protection model." Wu, Qiang (ed.) 8th IEEE International Conference on Computer and Information Technology. Sydney, Australia 08 - 11 Jul 2008 United States. https://doi.org/10.1109/CIT.2008.4594650
On the complexity of restricted k-anonymity problem
Sun, Xiaoxun, Wang, Hua and Li, Jiuyong. 2008. "On the complexity of restricted k-anonymity problem." Yanchun, Zhang (ed.) 10th Asia-Pacific Web Conference (APWeb 2008). Shenyang, China 26 - 28 Apr 2008 Germany. Springer. https://doi.org/10.1007/978-3-540-78849-2_30
Algorithms for core stability, core largeness, exactness, and extendability of flow games
Fang, Qizhi, Fleischer, Rudolf, Li, Jian and Sun, Xiaoxun. 2010. "Algorithms for core stability, core largeness, exactness, and extendability of flow games ." Frontiers of Mathematics in China. 5 (1), pp. 47-63. https://doi.org/10.1007/s11464-009-0048-y
Validating privacy requirements in large survey rating data
Sun, Xiaoxun, Wang, Hua and Li, Jiuyong. 2011. "Validating privacy requirements in large survey rating data." Bessis, Nik and Xhafa, Fatos (ed.) Next generation data technologies for collective computational intelligence. Berlin, Germany. Springer. pp. 445-469
Satisfying privacy requirements: one step before anonymization
Sun, Xiaoxun, Wang, Hua and Li, Jiuyong. 2010. "Satisfying privacy requirements: one step before anonymization." Zaki, Mohammed Javeed, Yu, Jeffrey Xu, Ravindran, B. and Pudi, Vikram (ed.) 14th Pacific-Asia Conference on Knowledge Discovery and Data Mining (PAKDD 2010). Hyderabad, India 21 - 24 Jun 2010 Berlin, Germany. Springer. https://doi.org/10.1007/978-3-642-13657-3_21
Towards identify anonymization in large survey rating data
Sun, Xiaoxun and Wang, Hua. 2010. "Towards identify anonymization in large survey rating data." NSS 2010: 4th International Conference on Network and System Security . Melbourne, Australia 01 - 03 Sep 2010 Piscataway, NJ. United States. https://doi.org/10.1109/NSS.2010.11
Microdata protection through approximate microaggregation
Sun, Xiaoxun, Wang, Hua and Li, Jiuyong. 2009. "Microdata protection through approximate microaggregation." Mans, Bernard (ed.) 32nd Australasian Computer Science Conference (ACSC 2009). Wellington, New Zealand 19 - 23 Jan 2009 Adelaide, Australia.
Injecting purpose and trust into data anonymisation
Sun, Xiaoxun, Wang, Hua and Li, Jiuyong. 2009. "Injecting purpose and trust into data anonymisation." Cheung, David, Song, Il-Yeol, Chu, Wesley, Hu, Xiaohua and Lin, Jimmy (ed.) 18th ACM International Conference on Information and Knowledge Management (CIKM 2009) . Hong Kong, China 02 - 06 Nov 2009 New York, USA. https://doi.org/10.1145/1645953.1646166
Enhanced p-sensitive k-anonymity models for privacy preserving data publishing
Sun, Xiaoxun, Wang, Hua, Li, Jiuyong and Truta, Traian Marius. 2008. "Enhanced p-sensitive k-anonymity models for privacy preserving data publishing." Transactions on Data Privacy. 1 (2), pp. 53-66.
Priority driven K-anonymisation for privacy protection
Sun, Xiaoxun, Wang, Hua and Li, Jiuyong. 2008. "Priority driven K-anonymisation for privacy protection." Roddick, John F., Li, Jiuyong, Christen, Peter and Kennedy, Paul J. (ed.) 7th Australasian Data Mining Conference (AusDM 2008). Glenelg, Adelaide 27 - 28 Nov 2008 Gold Coast, Australia.
An efficient hash-based algorithm for minimal k-anonymity
Sun, Xiaoxun, Li, Min, Wang, Hua and Plank, Ashley. 2008. "An efficient hash-based algorithm for minimal k-anonymity." Dobbie, Gillian and Mans, Bernard (ed.) ACSC 2008: 31st Australasian Computer Science Conference. Wollongong, Australia 22 - 25 Jan 2008 Sydney, Australia.