The OEIS Foundation is supported by donations from users of the OEIS and by a grant from the Simons Foundation.

 Hints (Greetings from The On-Line Encyclopedia of Integer Sequences!)
 A003141 Minimal number of arcs whose reversal yields a transitive tournament. (Formerly M2334) 5
 0, 0, 0, 1, 1, 3, 4, 7, 8, 12, 15, 20, 22, 28 (list; graph; refs; listen; history; text; internal format)
 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, 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 Equals C(n, 2) - A001225. a(n) = A182079(n) iff n <= 9, thereafter a(n) > A182079(n). [Bermond] Sequence in context: A129819 A025032 A207524 * A284491 A284506 A157419 Adjacent sequences:  A003138 A003139 A003140 * A003142 A003143 A003144 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

Lookup | Welcome | Wiki | Register | Music | Plot 2 | Demos | Index | Browse | More | WebCam
Contribute new seq. or comment | Format | Style Sheet | Transforms | Superseeker | Recent
The OEIS Community | Maintained by The OEIS Foundation Inc.

Last modified September 27 09:09 EDT 2020. Contains 337380 sequences. (Running on oeis4.)