An optimal algorithm for finding all convex subsets in tournaments (Q2760997)
From MaRDI portal
 | This is the item page for this Wikibase entity, intended for internal use and editing purposes. Please use this page instead for the normal view: An optimal algorithm for finding all convex subsets in tournaments |
scientific article; zbMATH DE number 1682811
| Language | Label | Description | Also known as |
|---|---|---|---|
| English | An optimal algorithm for finding all convex subsets in tournaments |
scientific article; zbMATH DE number 1682811 |
Statements
17 December 2001
0 references
tournament
0 references
convex set
0 references
transitive closure
0 references
An optimal algorithm for finding all convex subsets in tournaments (English)
0 references
The paper gives an \(O(n^3)\)-time algorithm for finding all convex sets in a tournament. An argument that the algorithm is asymptotically optimal is also given. The method uses a reduction to the transitive closure of a graph where an oriented edge expresses the fact that if the head belongs to a convex set then the same holds for the tail.
0 references
