Efficient Parallel Algorithms for some Tree Layout Problems

Dartmouth Technical Report PCS-TR93-189

	J. Diaz
	A. Gibbons
	Grammati E. Pantziou
	M. Serna
	Paul G. Spirakis
	J. Toran

Date:  1993

URL (PDF): <http://www.cs.dartmouth.edu/reports/TR93-189.pdf> (600KB)

Abstract:
 	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.