Accession Number : AD0779056

Title :   On the Computational Complexity of Finding Maxima of a Set of Vectors,

Corporate Author : CARNEGIE-MELLON 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 d-dimensional 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