File Download
There are no files associated with this item.
Links for fulltext
(May Require Subscription)
- Publisher Website: 10.1016/j.jctb.2019.08.004
- Scopus: eid_2-s2.0-85071286548
- WOS: WOS:000508288900012
- Find via
Supplementary
- Citations:
- Appears in Collections:
Article: Ranking Tournaments with No Errors I: Structural Description
Title | Ranking Tournaments with No Errors I: Structural Description |
---|---|
Authors | |
Keywords | Characterization Cycle packing Feedback arc set Minimax relation Tournament |
Issue Date | 2020 |
Publisher | Academic Press. The Journal's web site is located at http://www.elsevier.com/locate/jctb |
Citation | Journal of Combinatorial Theory, Series B, 2020, v. 141, p. 264-294 How to Cite? |
Abstract | 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 Möbius ladders as a subgraph; such a tournament is referred to as Möbius-free. In this first paper we present a structural description of all Möbius-free tournaments, which relies heavily on a chain theorem concerning internally 2-strong tournaments. © 2019 Elsevier Inc. |
Description | Bronze open access |
Persistent Identifier | http://hdl.handle.net/10722/289730 |
ISSN | 2023 Impact Factor: 1.2 2023 SCImago Journal Rankings: 1.793 |
ISI Accession Number ID |
DC Field | Value | Language |
---|---|---|
dc.contributor.author | Chen, X | - |
dc.contributor.author | Ding, G | - |
dc.contributor.author | Zang, W | - |
dc.contributor.author | Zhao, Q | - |
dc.date.accessioned | 2020-10-22T08:16:38Z | - |
dc.date.available | 2020-10-22T08:16:38Z | - |
dc.date.issued | 2020 | - |
dc.identifier.citation | Journal of Combinatorial Theory, Series B, 2020, v. 141, p. 264-294 | - |
dc.identifier.issn | 0095-8956 | - |
dc.identifier.uri | http://hdl.handle.net/10722/289730 | - |
dc.description | Bronze open access | - |
dc.description.abstract | 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 Möbius ladders as a subgraph; such a tournament is referred to as Möbius-free. In this first paper we present a structural description of all Möbius-free tournaments, which relies heavily on a chain theorem concerning internally 2-strong tournaments. © 2019 Elsevier Inc. | - |
dc.language | eng | - |
dc.publisher | Academic Press. The Journal's web site is located at http://www.elsevier.com/locate/jctb | - |
dc.relation.ispartof | Journal of Combinatorial Theory, Series B | - |
dc.subject | Characterization | - |
dc.subject | Cycle packing | - |
dc.subject | Feedback arc set | - |
dc.subject | Minimax relation | - |
dc.subject | Tournament | - |
dc.title | Ranking Tournaments with No Errors I: Structural Description | - |
dc.type | Article | - |
dc.identifier.email | Zang, W: wzang@maths.hku.hk | - |
dc.identifier.authority | Zang, W=rp00839 | - |
dc.description.nature | link_to_OA_fulltext | - |
dc.identifier.doi | 10.1016/j.jctb.2019.08.004 | - |
dc.identifier.scopus | eid_2-s2.0-85071286548 | - |
dc.identifier.hkuros | 317360 | - |
dc.identifier.volume | 141 | - |
dc.identifier.spage | 264 | - |
dc.identifier.epage | 294 | - |
dc.identifier.isi | WOS:000508288900012 | - |
dc.publisher.place | United States | - |
dc.identifier.issnl | 0095-8956 | - |