Tech Report CS-88-21
Parallel Constraint Graph Generation
John E. Savage and Markus G. Wloka
December 1988
Abstract:
In this paper we present a parallel algorithm for computing the {\em transitive reduction of an interval DAG}. This is equivalent to a parallel algorithm for computing a minimum-distance constraint DAG from a VLSI layout. An intermediate result developed during the execution of the above algorithm is a parallel algorithm for constructing a {\em tiling} or {\em corner stitching}, a geometrical data structure used in the Magic VLSI layout system. All these computations take time $O(\log ^ 2 n)$ using $O(n / \log n)$ processors on an EREW PRAM, so their processor-time product is optimal. The algorithm can easily be implemented on a practical parallel machine.
Order hardcopy report from techreports@cs.brown.edu