Network strength games: the core and the nucleolus

• 成果类型: Article
• 署名作者: Baiou, Mourad; Barahona, Francisco
• 署名单位: Centre National de la Recherche Scientifique (CNRS); Universite Clermont Auvergne (UCA); International Business Machines (IBM); IBM USA
• 刊物名称: MATHEMATICAL PROGRAMMING
• ISSN/ISSBN: 0025-5610
• DOI: 10.1007/s10107-018-1348-3
• 发表日期: 2020
• 页码: 117-136
• 关键词: Complexity; algorithm

摘要

The maximum number of edge-disjoint spanning trees in a network has been used as a measure of the strength of a network. It gives the number of disjoint ways that the network can be fully connected. This suggests a game theoretic analysis that shows the relative importance of the different links to form a strong network. We introduce the Network strength game as a cooperative game defined on a graph G=(V,E). The player set is the edge-set E and the value of a coalition S subset of Eis the maximum number of disjoint spanning trees included in S. We study the core of this game, and we give a polynomial combinatorial algorithm to compute the nucleolus when the core is non-empty.