Name
Abstract | ||
|---|---|---|
Cooperative matching games have drawn much interest partly because of the connection with bargaining solutions in the networking environment. However, it is not always guaranteed that a network under investigation gives rise to a stable bargaining outcome. To address this issue, we consider a modification process, called stabilization, that yields a network with stable outcomes, where the modification should be as small as possible. Therefore, the problem is cast to a combinatorial-optimization problem in a graph. Recently, the stabilization by edge removal was shown to be NP-hard. On the contrary, in this paper, we show that other possible ways of stabilization, namely, edge addition, vertex removal and vertex addition, are all polynomial-time solvable. Thus, we obtain a complete complexity-theoretic classification of the natural four variants of the network stabilization problem. We further study weighted variants and prove that the variants for edge addition and vertex removal are NP-hard. |
Year | DOI | Venue |
|---|---|---|
2017 | 10.1016/j.tcs.2017.03.020 | Theoretical Computer Science |
Keywords | DocType | Volume |
Cooperative game,Core,Gallai–Edmonds decomposition,Matching,Network bargaining,Solution concept | Journal | 677 |
ISSN | Citations | PageRank |
0304-3975 | 1 | 0.35 |
References | Authors | |
22 | 5 | |
Name | Order | Citations | PageRank |
|---|---|---|---|
| Takehiro Ito | 1 | 260 | 40.71 |
| Naonori Kakimura | 2 | 59 | 21.18 |
| Naoyuki Kamiyama | 3 | 80 | 23.40 |
| Yusuke Kobayashi | 4 | 106 | 21.98 |
| Yoshio Okamoto | 5 | 170 | 28.50 |