Output details

Coalition structure generation over graphs

Significance of output:

<12>This paper gives the analysis of the computational complexity of coalition structure generation (CSG) over graphs.

CSG is central to AI and multiagent systems, while graph clustering has been studied in theoretical computer science and operations research for specific valuation functions. This work for the first time brings together general valuations and graph structures. It has already achieved much attention from both communities, and inspired active work by Bachrach et al in Microsoft Cambridge (UK).

The model is supported by real-life scenarios, and its theoretical properties are extensively validated. The practical efficiency of algorithms is analytically proven by computational bounds.