cp's OEIS Frontend

A003141 Minimal number of arcs whose reversal yields a transitive tournament.

%I A003141 M2334 #60 Feb 14 2023 02:36:53
%S A003141 0,0,0,1,1,3,4,7,8,12,15,20,22,28
%N A003141 Minimal number of arcs whose reversal yields a transitive tournament.
%C A003141 This is the "minimum feedback arc set" problem.
%C A003141 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).
%D A003141 Sanchez-Flores, Neumann-Lara and Bermond, Graphs & Combin 10 (1994) 363-366 and 367-376.
%D A003141 N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).
%H A003141 J.-C. Bermond, <a href="http://www.numdam.org/item?id=MSH_1972__37__5_0">Ordres à distance minimum d'un tournoi et graphes partiels sans circuits maximaux</a>, Math. Sci. Hum., No. 37 (1972), 5-25.
%H A003141 J.-C. Bermond, <a href="/A003141/a003141.pdf">Ordres à distance minimum d'un tournoi et graphes partiels sans circuits maximaux</a>, Math. Sci. Hum., No. 37 (1972), 5-25. [Annotated scanned copy]
%H A003141 I. Charon and O. Hudry, <a href="http://biblio.telecom-paristech.fr/cgi-bin/download.cgi?id=9665">An updated survey on the linear ordering problem for weighted or unweighted tournaments</a>, Ann. Oper. Res. 175 (2010), 107-158
%H A003141 Don Coppersmith, Lisa Fleischer and Atri Rudra, <a href="http://www.cse.buffalo.edu/faculty/atri/papers/algos/FAS-journal-final.pdf">Ordering by weighted number of wins gives a good ranking for weighted tournaments</a>, SODA 2006: 776-782.
%H A003141 Robert A. Laird and Brandon S. Schamp, <a href="https://doi.org/10.1086/696266">Calculating Competitive Intransitivity: Computational Challenges</a>, The American Naturalist (2018), Vol. 191, No. 4, 547-552.
%H A003141 Range Voting Yahoo Group, <a href="http://groups.yahoo.com/group/RangeVoting/">Range Voting</a>.
%H A003141 Range Voting Yahoo Group, <a href="/A003141/a003141.txt">Introduction</a>. [Cached copy]
%H A003141 RangeVoting.org, <a href="https://rangevoting.org/">Group Website</a>.
%H A003141 K. B. Reid, <a href="http://dx.doi.org/10.4153/CMB-1969-032-x">On sets of arcs containing no cycles in tournaments</a>, Canad. Math. Bull., 12 (1969), 261-264.
%H A003141 W. D. Smith, <a href="http://rangevoting.org/PuzzDG.html">Partial Answer to Puzzle #21: Getting rid of cycles in directed graphs</a> [Has much more information]
%H A003141 <a href="/index/To#tournament">Index entries for sequences related to tournaments</a>
%F A003141 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
%Y A003141 Equals C(n, 2) - A001225.
%Y A003141 a(n) = A182079(n) iff n <= 9, thereafter a(n) > A182079(n). [Bermond]
%K A003141 hard,more,nonn,nice
%O A003141 0,6
%A A003141 _N. J. A. Sloane_
%E A003141 More terms from Irène Charon and Olivier Hudry
%E A003141 Terms a(12) and a(13) from _Christian Stricker_, Jan 14 2017