MULTILIST LAYERING - COMPLEXITY AND APPLICATIONS

A natural combinatorial generalization of the convex layer problem, te rmed multilist layering, is introduced. It is observed to be P-complet e in the general case. When the number of lists or layer size are boun ded by s(n), multilist layering is shown to be logspace-hard for the c lass 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, alm ost complete problem for Steve's classes SC1, SC2,.... is in particula r 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 r esult, the first NC solutions (SC solutions, respectively) for the con vex layer problem where the number of orientations or the layer size a re bonded by a constant (polylog bounded, respectively) are derived.