Accession Number:

AD0779056

Title:

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

Descriptive Note:

Corporate Author:

CARNEGIE-MELLON UNIV PITTSBURGH PA DEPT OF COMPUTER SCIENCE

Personal Author(s):

Report Date:

1974-04-01

Pagination or Media Count:

19.0

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 dn. Modified author abstract

Subject Categories:

  • Theoretical Mathematics

Distribution Statement:

APPROVED FOR PUBLIC RELEASE