• Complex
  • Title
  • Keyword
  • Abstract
  • Scholars
  • Journal
  • ISSN
  • Conference
成果搜索

author:

Hu, Shanli (Hu, Shanli.) [1] | Li, Shaofang (Li, Shaofang.) [2] | Shi, Chunyi (Shi, Chunyi.) [3]

Indexed by:

EI Scopus PKU CSCD

Abstract:

Coalition formation is a key topic in multi-agent systems. However, finding the optimal coalition structure is NP-complete. Sandholm et al. show that it is necessary and sufficient to search the lowest two levels of the coalition structure graph in order to establish a worst-case bound k. How to do a further search after the lowest two levels of the coalition structure graph is a problem which hasn't been resolved for a long time. Dang et al. have presented an algorithm: for the odd bound k3, those coalition structures are further searched whose biggest coalition's cardinality is not less than ⌈n(k-1)/(k+1)⌉, which is the first algorithm known whose searching unit is not level and it is obviously faster than that of Sandholm et al for the smaller bound. The authors analyze the relations among coalition structures deeply and present an algorithm that only needs to search those coalition structures whose biggest coalition's cardinality is equal to ⌈n(k-1)/(k+1)⌉ to decrease largely the number of coalition structures needed to be searched. Moreover, the algorithm is improved to search skillfully those corresponding levels whose coalition structures are fewer than some of those coalition structures whose biggest coalition's cardinality is equal to ⌈n(k-1)/(k+1)⌉, therefore decreasing further the number of coalition structures needed to be searched and improving largely the work of Sandholm et al. and Dang et al.

Keyword:

Graph structures Multi agent systems Structural optimization

Community:

  • [ 1 ] [Hu, Shanli]Department of Computer Science and Technology, Fuzhou University, Fuzhou 350108, China
  • [ 2 ] [Li, Shaofang]Department of Electronic Information Engineering, Putian College, Putian, Fujian 351100, China
  • [ 3 ] [Shi, Chunyi]Department of Computer Science and Technology, Tsinghua University, Beijing 100084, China

Reprint 's Address:

Show more details

Related Keywords:

Related Article:

Source :

Computer Research and Development

ISSN: 1000-1239

CN: 11-1777/TP

Year: 2009

Issue: 8

Volume: 46

Page: 1357-1363

Cited Count:

WoS CC Cited Count:

SCOPUS Cited Count:

ESI Highly Cited Papers on the List: 0 Unfold All

WanFang Cited Count:

Chinese Cited Count:

30 Days PV: 2

Online/Total:96/10036391
Address:FZU Library(No.2 Xuyuan Road, Fuzhou, Fujian, PRC Post Code:350116) Contact Us:0591-22865326
Copyright:FZU Library Technical Support:Beijing Aegean Software Co., Ltd. 闽ICP备05005463号-1