Multilist layering: Complexity and applications

AbstractA 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