PARALLEL ALGORITHMS FOR THE MINIMUM CUT AND THE MINIMUM LENGTH TREE LAYOUT PROBLEMS

The minimum cut and minimum length linear arrangement problems usually occur in solving wiring problems and have a lot in common with job se quencing questions. Both problems are NP-complete for general graphs a nd in P for trees. We present here two parallel algorithms for the CRE W PRAM. The first solves the minimum length linear arrangement problem for trees and the second solves the minimum cut arrangement for trees . We prove that the first problem belongs to NC for trees, and the sec ond problem is in NC for bounded degree trees. To the best of our know ledge, these are the first parallel algorithms for the minimum length and the minimum cut linear arrangement problems.