Tournament Ranking with Expected Profit in Polynomial Time

DOI10.1137/0401037zbMath0667.05030OpenAlexW2061848409MaRDI QIDQ3819090

Vojtěch Rödl, Svatopluk Poljak, J. H. Spencer

Publication date: 1988

Published in: SIAM Journal on Discrete Mathematics (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1137/0401037

zbMATH Keywords

rankingNP-completetournament ranking problem

Mathematics Subject Classification ID

Graph theory (05C99) Directed graphs (digraphs), tournaments (05C20)

Related Items

A new algorithm for ranking players of a round-robin tournament, A survey on the linear ordering problem for weighted or unweighted tournaments, Extremal results on feedback arc sets in digraphs, Invertibility of Digraphs and Tournaments, Intersections of random hypergraphs and tournaments, Voting Procedures, Complexity of, On existence theorems, An updated survey on the linear ordering problem for weighted or unweighted tournaments, An improved MST algorithm for ranking players of a round-robin tournament, Checking robust nonsingularity is NP-hard