EUVIMEDEUVIMED entdecken
Open Access · CC BY 4.0

Arboricity games: the core and the nucleolus

Han Xiao, Qizhi Fang

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.

AbstractBibliografische AngabenZitierenVerwandte Studien

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}
}
Kostenlos starten →