On the Computational Complexity of Finding Maxima of a Set of Vectors,
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)
Document Details
- Document Type
- Technical Report
- Publication Date
- Apr 01, 1974
- Accession Number
- AD0779056
Entities
People
- H. T. Kung
Organizations
- Carnegie Mellon University