• 主题
高级搜索  >
历史搜索 清空历史
首页> 外文期刊>Journal of Combinatorial Theory, Series B >Ranking tournaments with no errors I: Structural description
【24h】

Ranking tournaments with no errors I: Structural description

机译：没有错误的锦标赛I：结构描述

获取原文
获取原文并翻译 | 示例
           
页面导航
  • 摘要
  • 著录项
  • 相似文献
  • 相关主题

摘要

In this series of two papers we examine the classical problem of ranking a set of players on the basis of a set of pairwise comparisons arising from a sports tournament, with the objective of minimizing the total number of upsets, where an upset occurs if a higher ranked player was actually defeated by a lower ranked player. This problem can be rephrased as the so-called minimum feedback arc set problem on tournaments, which arises in a rich variety of applications and has been a subject of extensive research. In this series we study this NP-hard problem using structure-driven and linear programming approaches. Let T = (V, A) be a tournament with a nonnegative integral weight w(e) on each arc e. A subset F of arcs is called a feedback arc set if TF contains no cycles (directed). A collection C of cycles (with repetition allowed) is called a cycle packing if each arc e is used at most w(e) times by members of C. We call T cycle Mengerian (CM) if, for every nonnegative integral function w defined on A, the minimum total weight of a feedback arc set is equal to the maximum size of a cycle packing. The purpose of these two papers is to show that a tournament is CM iff it contains none of four Mobius ladders as a subgraph; such a tournament is referred to as Mobius-free. In this first paper we present a structural description of all Mobius-free tournaments, which relies heavily on a chain theorem concerning internally 2-strong tournaments. (C) 2019 Elsevier Inc. All rights reserved.
机译：在这一系列的两篇论文中，我们根据运动锦标赛产生的一组成对比较来研究一组球员排名一组球员的经典问题，目的是最大限度地减少扰乱总数，如果更高的情况排名球员实际上被一个较低的球员击败了。这个问题可以被重建，因为锦标赛上所谓的最小反馈弧形阵列问题，它在丰富的各种应用中出现，并且是一项广泛研究的主题。在本系列中，我们使用结构驱动和线性编程方法研究了这种NP难题。设t =（v，a）是每个电弧e上具有非负积分权重w（e）的锦标赛。如果T f不包含循环（定向），则弧的子集F称为反馈弧。如果每个ARC E由C的大多数w（e）次使用，则循环（允许重复允许的重复）被称为周期包装。如果为每个非负积分函数W调用t循环媒体（cm），则每个arc e呼叫t循环媒体（cm）在A中，反馈电弧集的最小总重量等于周期包装的最大尺寸。这两篇论文的目的是表明锦标赛是CM IFF，它不包含四个Mobius梯子作为子图;这样的锦标赛被称为移动莫瑞斯。在本第一篇论文中，我们提出了所有移动性锦标赛的结构描述，这在严重依赖于内部2强锦标赛的链式定理。 （c）2019 Elsevier Inc.保留所有权利。

著录项

相似文献

  • 外文文献
  • 中文文献
  • 专利
获取原文

客服邮箱：kefu@zhangqiaokeyan.com

京公网安备：11010802029741号 ICP备案号：京ICP备15016152号-6 六维联合信息科技 (北京) 有限公司©版权所有

  • 客服微信

  • 服务号