1993
Multi-list ranking: Complexity and applications
Publication
Publication
A natural combinatorial generalization of the convex layer problem, termed multi-list ranking, is introduced. It is proved to be P-complete in the general case. When the number of lists or layer size are bounded by s(n), multi-list ranking is shown to be log-space hard for the class of problems solvable simultaneously in polynomial time and space s(n). On the other hand, simultaneous polynomial-time and 0(s(n) log n)-space solutions in the above cases are provided. Also, NC algorithms for multilist ranking when the number of lists or layer size are constantly bounded are given. In result, the first NC solutions (SC solutions, respectively) for the convex layer problem where the number of orientations or the layer size are constantly bounded (poly-log bounded, respectively) are derived.
Additional Metadata | |
---|---|
Lecture Notes in Computer Science | |
Organisation | Computational Geometry Lab |
Dessmark, A. (Anders), Lingas, A. (Andrzej), & Maheshwari, A. (1993). Multi-list ranking: Complexity and applications. In Lecture Notes in Computer Science.
|