Name
Abstract | ||
|---|---|---|
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 that every nontrivial convex subset is the closure of a subset of vertices of cardinality two. This result leads to algorithms that find all convex subsets in a tournament in $O(n^4)$ serial time and in $O(\log ^2 n)$ parallel time using $O(n^4)$ processors. Several variations of the problem that are solvable with this new algorithm are also presented. |
Year | DOI | Venue |
|---|---|---|
1996 | 10.1137/S0895480193251234 | SIAM J. Discrete Math. |
Keywords | Field | DocType |
vertex subset,convex subsets,nontrivial convex subset,convex subset,new algorithm,parallel time,serial time,two-path beginning | Discrete mathematics,Combinatorics,Convex combination,Counting measure,Convex hull,Logarithmically convex function,Convex set,Subderivative,Convex polytope,Mathematics,Convex cone | Journal |
Volume | Issue | ISSN |
9 | 1 | 0895-4801 |
Citations | PageRank | References |
6 | 1.31 | 0 |
Authors | ||
2 | ||
Name | Order | Citations | PageRank |
|---|---|---|---|
| David J. Haglin | 1 | 112 | 19.45 |
| Marty J. Wolf | 2 | 85 | 17.50 |