Multilist layering: Complexity and applications
A natural combinatorial generalization of the convex layer problem, termed multilist layering, is introduced. It is observed to be P-complete in the general case. When the number of lists or layer size are bounded by s(n), multilist layering is shown to be logspace-hard for the class of problems solvable simultaneously in polynomial time and space s(n). On the other hand, simultaneous polynomial-time and O(s(n) log n)-space solutions in the above cases are provided. Thus a natural, almost complete problem for Steve's classes SC1,SC2,/4. is in particular obtained. Also, NC algorithms for multilist layering when the number of lists or the layer size is bounded by a constant are given. As a result, the first NC solutions (SC solutions, respectively) for the convex layer problem where the number of orientations or the layer size are bonded by a constant (polylog bounded, respectively) are derived.
|Journal||Theoretical Computer Science|
Dessmark, A. (Anders), Lingas, A. (Andrzej), & Maheshwari, A. (1995). Multilist layering: Complexity and applications. Theoretical Computer Science, 141(1-2), 337–350. doi:10.1016/0304-3975(94)00213-3