
Accession Number : AD0779056
Title : On the Computational Complexity of Finding Maxima of a Set of Vectors,
Corporate Author : CARNEGIEMELLON UNIV PITTSBURGH PA DEPT OF COMPUTER SCIENCE
Personal Author(s) : Kung,H. T.
Report Date : APR 1974
Pagination or Media Count : 19
Abstract : Let (U sub 1), (U sub 2),...., (U sub d) be totally ordered sets and let V be a set of n ddimensional vectors in (U sub 1) x (U sub 2) x...x (U sub d). A partial ordering is defined on V in a natural way. The author considers the problem of finding all maximal elements of V with respect to the partial ordering. The computational complexity of the problem is defined to be the number of required comparisons of two components and is denoted by (C sub d(n)). (Modified author abstract)
Descriptors : *Set theory, *Computations, Algorithms, Recursive functions, Theorems
Subject Categories : Theoretical Mathematics
Distribution Statement : APPROVED FOR PUBLIC RELEASE