An Optimal Algorithm for Finding All Convex Subsets in Tournaments

A tournament is a complete directed graph. A convex subset is a vertex subset with the property that every two-path beginning and ending inside the convex subset is contained completely within the subset. This paper shows a relationship between convex subsets and transitive closures which leads to an optimal \(O(n^3)\)-time algorithm for finding all convex subsets in a tournament.