An Optimal Algorithm for Finding All Convex Subsets in Tournaments.
Marty J. Wolf, David J. Haglin · 1999
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. This research was supported in part by a Mankato State University Academic Affairs Research Fund grant. 1 Introduction A tournament is a directed graph on n vertices that is obtained by directing all of the edges in a complete undirected graph. A convex subset is a subset of the vertices such that any vertex not in the subset either dominates or is dominated by all of the vertices in the convex subset. Alternatively, a subset C ` V is convex if and only if every two path u ! w ! v, where u; v 2 C implies w 2 C. Although it is known that a single convex subset can be found in O(n 3 ) time [2], our algo...