论文标题
树木游戏：核心和核仁
Arboricity games: the core and the nucleolus
论文作者
论文摘要
图形的树木性是覆盖其所有边缘所需的最小森林数量。在本文中，我们从游戏理论的角度研究了建立树木，并研究了最低森林覆盖问题的成本分布。我们将树木游戏游戏介绍为图表上定义的合作成本游戏。球员是边缘，每个联盟的成本都是联盟诱导的子图的树木。我们研究核心的性质，并提出一种有效的算法，用于计算核仁时，当核心不为空时。为了计算核心中的核仁，我们介绍了基于最密集的子图晶格建立的质量分区。 Prime分区将图的边缘集分解为由最小密度未成年人及其不变优先级的部分定义的部分排序集。此外，来自同一分区的边缘在核心分配中始终具有相同的值。因此，当核心不为空时，素数会显着减少马斯勒方案线性程序中所需的变量和约束的数量，并允许我们在多项式时间内计算核仁。此外，主要分区提供了类似于著名的核心分解和密度友好分解的图形分解，这可能具有独立的兴趣。
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.
