Arboricity games: the core and the nucleolus
Mathematical Programming · 2023-03 · 198 (1) · 1-25
DOI: 10.1007/s10107-021-01752-w ↗Kurz gefasst
Fachartikel in der Zeitschrift Mathematical Programming, online erschienen am 29.01.2022. Verfasst von Han Xiao und 1 weiteren Autor:innen. Die Arbeit wurde bisher 3-mal zitiert (Crossref) und nennt 35 Literaturangaben. Der Volltext ist frei zugänglich (Open Access, CC BY 4.0). Gefördert von: National Natural Science Foundation of China, Natural Science Foundation of Shandong Province.
Abstract (Originalsprache)
The arboricity of a graph is the minimum number of forests required to cover all its edges. In this paper, we examine arboricity from a game-theoretic perspective and investigate cost-sharing in the minimum forest cover problem. We introduce the arboricity game as a cooperative cost game defined on a graph. The players are edges, and the cost of each coalition is the arboricity of the subgraph induced by the coalition. We study properties of the core and propose an efficient algorithm for computing the nucleolus when the core is not empty. In order to compute the nucleolus in the core, we introduce the prime partition which is built on the densest subgraph lattice. The prime partition decomposes the edge set of a graph into a partially ordered set defined from minimal densest minors and their invariant precedence relation. Moreover, edges from the same partition always have the same value in a core allocation. Consequently, when the core is not empty, the prime partition significantly reduces the number of variables and constraints required in the linear programs of Maschler’s scheme and allows us to compute the nucleolus in polynomial time. Besides, the prime partition provides a graph decomposition analogous to the celebrated core decomposition and the density-friendly decomposition, which may be of independent interest.
Förderung
- National Natural Science Foundation of China
- Natural Science Foundation of Shandong Province
Zitieren
APA
Xiao, H., & Fang, Q. (2023). Arboricity games: the core and the nucleolus. Mathematical Programming, 198(1), 1-25. https://doi.org/10.1007/s10107-021-01752-w
Vancouver
Xiao H, Fang Q. Arboricity games: the core and the nucleolus. Mathematical Programming. 2023;198(1):1-25. doi:10.1007/s10107-021-01752-w
BibTeX
@article{Xiao2023,
author = {Xiao, Han and Fang, Qizhi},
title = {Arboricity games: the core and the nucleolus},
journal = {Mathematical Programming},
year = {2023},
volume = {198},
number = {1},
pages = {1--25},
doi = {10.1007/s10107-021-01752-w}
}
EUVIMED