OFFSET
0,6
COMMENTS
This is the "minimum feedback arc set" problem.
The minimal number of arcs you need to delete to make a directed graph acyclic (maxed over all n-vertex directed graphs) is the same as the minimal number of arcs you need to reverse to make a tournament acyclic (maxed over all n-player tournaments).
REFERENCES
Sanchez-Flores, Neumann-Lara and Bermond, Graphs & Combin 10 (1994) 363-366 and 367-376.
N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).
LINKS
J.-C. Bermond, Ordres à distance minimum d'un tournoi et graphes partiels sans circuits maximaux, Math. Sci. Hum., No. 37 (1972), 5-25.
J.-C. Bermond, Ordres à distance minimum d'un tournoi et graphes partiels sans circuits maximaux, Math. Sci. Hum., No. 37 (1972), 5-25. [Annotated scanned copy]
I. Charon and O. Hudry, An updated survey on the linear ordering problem for weighted or unweighted tournaments, Ann. Oper. Res. 175 (2010), 107-158
Don Coppersmith, Lisa Fleischer and Atri Rudra, Ordering by weighted number of wins gives a good ranking for weighted tournaments, SODA 2006: 776-782.
Robert A. Laird and Brandon S. Schamp, Calculating Competitive Intransitivity: Computational Challenges, The American Naturalist (2018), Vol. 191, No. 4, 547-552.
Range Voting Yahoo Group, Range Voting.
Range Voting Yahoo Group, Introduction. [Cached copy]
RangeVoting.org, Group Website.
K. B. Reid, On sets of arcs containing no cycles in tournaments, Canad. Math. Bull., 12 (1969), 261-264.
W. D. Smith, Partial Answer to Puzzle #21: Getting rid of cycles in directed graphs [Has much more information]
FORMULA
The asymptotics for large n are (n+1)*n/4 - C*n^(3/2) <= F(n) <= (n+1)*n/4 - K*n^(3/2) for all sufficiently large n and certain constants C, K > 0. - Warren D. Smith, Sep 14 2006
CROSSREFS
KEYWORD
hard,more,nonn,nice
AUTHOR
EXTENSIONS
More terms from Irène Charon and Olivier Hudry
Terms a(12) and a(13) from Christian Stricker, Jan 14 2017
STATUS
approved