AbstractThe set maxima problem is defined as follows: given a totally ordered universe X of size n and S subseteq 2^X, |S| = n, find max S for all S in S. It has been conjectured that this problem can be solved deterministically with O(n) comparisons. In this paper, we discuss the proposal of Komlos that the minimum spanning tree verification algorithm should provide a solution paradigm for the set maxima problem. We generalize Komlos' algorithm to a larger set of problems arising from the verification of the optimum basis of a very large class of matroids. We will also provide an algorithm for the complementary case of maxima over fundamental matroid hyperplanes.
RightsThis Item is protected by copyright and/or related rights.You are free to use this Item in any way that is permitted by the copyright and related rights legislation that applies to your use.For other uses you need to obtain permission from the rights-holder(s).