Ranking tournaments with no errors. II: Minimax relation

DOI10.1016/j.jctb.2019.10.004zbMath1437.05085OpenAlexW2981646601MaRDI QIDQ1985451

Wenan Zang, Guoli Ding, Qiu-Lan Zhao, Xu-jin Chen

Publication date: 7 April 2020

Published in: Journal of Combinatorial Theory. Series B (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.jctb.2019.10.004

zbMATH Keywords

algorithmdualitytournamentfeedback arc setintegrality

Mathematics Subject Classification ID

Linear programming (90C05) Directed graphs (digraphs), tournaments (05C20) Signed and weighted graphs (05C22)

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Packing directed circuits exactly
• Integral infeasibility and testing total dual integrality
• The ellipsoid method and its consequences in combinatorial optimization
• The matroids with the max-flow min-cut property
• A short proof of Seymour's characterization of the matroids with the max-flow min-cut property
• Packing odd circuits in Eulerian graphs
• Packing cycles in graphs
• Packing cycles in graphs. II
• Combinatorial optimization. Polyhedra and efficiency (3 volumes)
• Packing circuits in eulerian digraphs
• Ranking tournaments with no errors. I: Structural description
• An Approximation Algorithm for Feedback Vertex Sets in Tournaments
• A Minimax Theorem for Directed Graphs
• Compositions of Graphs and Polyhedra IV: Acyclic Spanning Subgraphs
• Max-Flow Min-Cut Matroids: Polynomial Testing and Polynomial Algorithms for Maximum Flow and Shortest Routes