A connection between sports and matroids: how many teams can we beat?

DOI10.1007/s00453-016-0256-2zbMath1406.05015OpenAlexW2557657806MaRDI QIDQ1702129

Ildikó Schlotter, Katarína Cechlárova

Publication date: 28 February 2018

Published in: Algorithmica (Search for Journal in Brave)

Full work available at URL: http://real.mtak.hu/61819/1/mbc.pdf

zbMATH Keywords

approximationmatroidsgraph labellingparameterized complexitysports elimination problemgammoids

Mathematics Subject Classification ID

Matroids in convex geometry (realizations in the context of convex polytopes, convexity in combinatorial structures, etc.) (52B40) Combinatorial aspects of matroids and geometric lattices (05B35) Graph labelling (graceful graphs, bandwidth, etc.) (05C78)

Related Items (1)

Correction to: ``A connection between sports and matroids: how many teams can we beat?

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Fundamentals of parameterized complexity
• Baseball playoff eliminations: An application of linear programming. Erratum
• Refining the complexity of the sports elimination problem
• Clustering to minimize the maximum intercluster distance
• Planar orientations with low out-degree and compaction of adjacency matrices
• A fast algorithm for the generalized parametric minimum cut problem and applications
• Minimum perfect bipartite matchings and spanning trees under categorization
• Lattice structures from planar graphs
• Upper and lower degree-constrained graph orientation with minimum penalty
• The computational complexity of the elimination problem in generalized sports competitions
• Applications of Menger's graph theorem
• On the degrees of the vertices of a directed graph
• A New Property and a Faster Algorithm for Baseball Elimination
• Parameterized Complexity of Induced H-Matching on Claw-Free Graphs
• Fast Algorithms for Parametric Scheduling Come From Extensions to Parametric Maximum Flow
• This House Proves that Debating is Harder than Soccer
• Possible Winners in Partially Completed Tournaments
• The new FIFA rules are hard: Complexity aspects of sports competitions.
• The structure and complexity of sports elimination numbers
• Degree-constrained orientations of embedded graphs

This page was built for publication: A connection between sports and matroids: how many teams can we beat?