Name
Abstract | ||
|---|---|---|
We examine the size s(n) of a smallest tournament having the arcs of an acyclic tournament on n vertices as a minimum feedback arc set. Using an integer linear programming formulation we obtain lower bounds s(n)‚ 3n¡ 2¡blog2nc or s(n)‚ 3n¡ 1¡blog2nc, depending on the binary expansion of n .W henn =2 k¡ 2t we show that the bounds are tight with s(n )= 3n¡2¡blog2nc. One view of this problem is that if the 'teams' in a tournament are ranked to minimize inconsistencies there is some tournament with s(n) 'teams' in which n are ranked wrong. We will also pose some questions about conditions on feedback arc sets, motivated by our proofs, which ensure equality between the maximum number of arc disjoint cycles and the minimum size of a feedback arc set in a tournament. AMS Classiflcation: Primary 05C20; Secondary 68R10 |
Year | Venue | Keywords |
|---|---|---|
1995 | Electr. J. Comb. | lower bound |
Field | DocType | Volume |
Discrete mathematics,Tournament,Combinatorics,Disjoint sets,Arc (geometry),Vertex (geometry),Integer programming,Mathematical proof,Mathematics,Feedback arc set,Binary number | Journal | 2 |
Citations | PageRank | References |
4 | 0.75 | 4 |
Authors | ||
1 | ||
Name | Order | Citations | PageRank |
|---|---|---|---|
| Garth Isaak | 1 | 172 | 24.01 |