We found a match
Your institution may have access to this item. Find your institution then sign in to continue.
- Title
Network strength games: the core and the nucleolus.
- Authors
Baïou, Mourad; Barahona, Francisco
- Abstract
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 ⊆ E is 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.
- Subjects
NUCLEOLUS; SPANNING trees; NONCOOPERATIVE games (Mathematics); GAMES
- Publication
Mathematical Programming, 2020, Vol 180, Issue 1/2, p117
- ISSN
0025-5610
- Publication type
Article
- DOI
10.1007/s10107-018-1348-3