%T Efficient Parallel Algorithms for some Tree Layout Problems
%A J. Diaz
%A A. Gibbons
%A Grammati E. Pantziou
%A M. Serna
%A Paul G. Spirakis
%A J. Toran
%R Technical Report PCS-TR93-189
%I Dartmouth College, Computer Science
%C Hanover, NH
%D  1993
%U http://www.cs.dartmouth.edu/reports/TR93-189.pdf
%X
 	The minimum cut and minimum length linear arrangement problems
 usually occur in solving wiring problems and have a lot in common with
 job sequencing questions. Both problems are NP-complete for general
 graphs and in P for trees. We present here two algorithms in NC. The
 first solves the minimum length linear arrangement problem for
 unrooted trees in $O(\log^2 n)$ time and $O(n^2 3^{\log n})$ CREW PRAM
 processors. The second algorithm solves the minimum cut arrangement
 for unrooted trees of maximum degree $d$ in $O(d \log^2 n)$ time and
 $O(n^2 /\log n)$ CREW PRAM processors.