Parallel constraint graph generation
John E. Savage, Markus G. Wloka · 1989
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.