Ranking tournaments with no errors II: Minimax relation
Ranking tournaments with no errors II: Minimax relation
复制标题
无错误排名赛 II：Minimax 关系
DOI：
10.1016/j.jctb.2019.10.004
复制
发表时间：
2020
期刊：
影响因子：
--
通讯作者：
Zhao Qiulan
中科院分区：
文献类型：
--
作者：
Chen Xujin;Ding Guoli;Zang Wenan;Zhao Qiulan
一个竞赛图T=（V，A）称为圈Mengerian（CM），如果它对定义在A上的每个非负整权函数满足关于填充和覆盖圈的极大极小关系。这一系列的两篇论文的目的是证明一个竞赛图是CM当且仅当它不包含四个莫比乌斯梯作为子图;这样的竞赛图被称为莫比乌斯自由图。在第一篇论文中，我们给出了所有Möbius自由竞赛图的结构描述，并证明了每一个CM竞赛图都是Möbius自由的。在第二篇论文中，我们通过使用我们的结构定理和线性规划方法建立了相反的关系。
Abstract A tournament T=(V, A) is called cycle Mengerian (CM) if it satisfies the minimax relation on packing and covering cycles, for every nonnegative integral weight function defined on A. The purpose of this series of two papers is to show that a tournament is CM iff it contains none of four Möbius ladders as a subgraph; such a tournament is referred to as Möbius-free. In the first paper we have given a structural description of all Möbius-free tournaments, and have proved that every CM tournament is Möbius-free. In this second paper we establish the converse by using our structural theorems and linear programming approach.