Algorithms for core stability, core largeness, exactness, and extendability of flow games

Paper

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
Paper/Presentation Title

Algorithms for core stability, core largeness, exactness, and extendability of flow games

Presentation TypePaper
AuthorsFang, Qizhi (Author), Fleischer, Rudolf (Author), Li, Jian (Author) and Sun, Xiaoxun (Author)
EditorsLin, G.
Journal or Proceedings TitleLecture Notes in Computer Science (Book series)
Journal Citation4598, pp. 439-447
Number of Pages9
Year2007
PublisherSpringer
Place of PublicationBerlin, Germany
ISSN1611-3349
0302-9743
ISBN9783540735441
Digital Object Identifier (DOI)https://doi.org/10.1007/978-3-540-73545-8_43
Web Address (URL) of Paperhttp://www.springerlink.com/content/pg4473643h383731/?MUD=MP
Conference/EventCOCOON 2007: 13th Annual International Computing and Combinatorics Conference
Event Details
COCOON 2007: 13th Annual International Computing and Combinatorics Conference
Event Date
16 to end of 19 Jul 2007
Event Location
Banff, Canada
Abstract

In this paper, we give linear time algorithms to decide core
stability, core largeness, exactness, and extendability of flow games on uniform networks (all edge capacities are 1). We show that a uniform flow game has a stable core if and only if the network is a balanced DAG (for all non-terminal vertices, indegree equals outdegree), which can be decided in linear time. Then we show that uniform flow games are exact, extendable, and have a large core if and only if the network is a balanced directed series-parallel graph, which again can be decided in linear time.

Keywordsalgorithms; computer graphics; linear programming; flow games; linear time algorithms; game theory
ANZSRC Field of Research 2020490302. Numerical analysis
461399. Theory of computation not elsewhere classified
460702. Computer graphics
Public Notes

Files associated with this item cannot be displayed due to copyright restrictions.

Byline AffiliationsOcean University of China, China
Fudan University, China
Department of Mathematics and Computing
Institution of OriginUniversity of Southern Queensland
Permalink -

https://research.usq.edu.au/item/q181y/algorithms-for-core-stability-core-largeness-exactness-and-extendability-of-flow-games

Log in to edit
  • 1751
    total views
  • 5
    total downloads
  • 0
    views this month
  • 0
    downloads this month

Export as

Related outputs

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
Finding nucleolus of flow game
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
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.