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

DOI10.1007/S00453-016-0256-2MaRDI QIDQ1702129zbMATH OpenOpenAlexFDO

Authors Ildikó Schlotter, Katarina Cechlárová

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

approximationparameterized complexitymatroidsgraph labellingsports 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)

Recommendations

• The computational complexity of the elimination problem in generalized sports competitions
• The structure and complexity of sports elimination numbers
• Tournament scoring problem
• A new property and a faster algorithm for baseball elimination
• Refining the complexity of the sports elimination problem

Cites work

• scientific article; zbMATH DE number 6474898 (Why is no real title available?)
• scientific article; zbMATH DE number 3604926 (Why is no real title available?)
• scientific article; zbMATH DE number 3639144 (Why is no real title available?)
• scientific article; zbMATH DE number 1418355 (Why is no real title available?)
• scientific article; zbMATH DE number 2203240 (Why is no real title available?)
• scientific article; zbMATH DE number 3366749 (Why is no real title available?)
• A fast algorithm for the generalized parametric minimum cut problem and applications
• A new property and a faster algorithm for baseball elimination
• Applications of Menger's graph theorem
• Baseball playoff eliminations: An application of linear programming. Erratum
• Clustering to minimize the maximum intercluster distance
• Combinatorial optimization. Networks and matroids
• Degree-constrained orientations of embedded graphs
• Fast Algorithms for Parametric Scheduling Come From Extensions to Parametric Maximum Flow
• Fundamentals of parameterized complexity
• Lattice structures from planar graphs
• Minimum perfect bipartite matchings and spanning trees under categorization
• On the degrees of the vertices of a directed graph
• Parameterized complexity of induced H-matching on claw-free graphs
• Planar orientations with low out-degree and compaction of adjacency matrices
• Possible Winners in Partially Completed Tournaments
• Refining the complexity of the sports elimination problem
• The computational complexity of the elimination problem in generalized sports competitions
• The new FIFA rules are hard: Complexity aspects of sports competitions.
• The structure and complexity of sports elimination numbers
• This house proves that debating is harder than soccer
• Upper and lower degree-constrained graph orientation with minimum penalty

Cited in

(3)

• A new property and a faster algorithm for baseball elimination
• Correction to: ``A connection between sports and matroids: how many teams can we beat?
• Refining the complexity of the sports elimination problem

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

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1702129)