Title :
Time- and cost-optimal parallel algorithms for the dominance and visibility graphs [IC design]
Author :
Bhagavathi, D. ; Olariu, S. ; Schwing, J.L. ; Zhang, J.
Author_Institution :
Dept. of Comput. Sci., Old Dominion Univ., Norfolk, VA, USA
Abstract :
The compaction step of integrated circuit design motivates associating several kinds of graphs with a collection of non-overlapping rectangles in the plane. These graphs are intended to capture various visibility relations amongst the rectangles in the collection. The contribution of this paper is to propose time- and cost-optimal algorithms to construct two such graphs, namely, the dominance graph (DG, for short) and the visibility graph (VG, for short). Specifically, we show that with a collection of n non-overlapping rectangles as input, both these structures can be constructed in Θ(log n) time using n processors in the CREW model
Keywords :
circuit layout CAD; graph theory; integrated circuit technology; parallel algorithms; CREW model; IC design; compaction step; cost-optimal algorithms; dominance graph; integrated circuit design; nonoverlapping rectangles; parallel algorithms; time-optimal algorithms; visibility graph; Cities and towns; Compaction; Computer science; Costs; Design automation; Integrated circuit synthesis; Mathematics; NASA; Parallel algorithms; Phase change random access memory;
Conference_Titel :
VLSI Design, 1994., Proceedings of the Seventh International Conference on
Conference_Location :
Calcutta
Print_ISBN :
0-8186-4990-9
DOI :
10.1109/ICVD.1994.282654
