Time- and Cost-Optimal Parallel Algorithms for the Dominance and Visibility Graphs | Zendy

D. Bhagavathi | Zendy; H. Gurla | Zendy; Stephan Olariu | Zendy; J.L. Schwing | Zendy; Jinming Zhang | Zendy

AI Assistant Blog Pricing

Home ZAIA Blog

Open Access

Time- and Cost-Optimal Parallel Algorithms for the Dominance and Visibility Graphs

Author(s) -

D. Bhagavathi,

H. Gurla,

Stephan Olariu,

J.L. Schwing,

Jinming Zhang

Publication year - 1993

Publication title -

vlsi design

Language(s) - English

Resource type - Journals

SCImago Journal Rank - 0.123

H-Index - 24

eISSN - 1065-514X

pISSN - 1026-7123

DOI - 10.1155/1996/40175

Subject(s) - visibility , visibility graph , computer science , algorithm , indifference graph , graph , dominance (genetics) , combinatorics , theoretical computer science , mathematics , geography , geometry , regular polygon , meteorology , biochemistry , chemistry , gene

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

The content you want is available to Zendy users.

Already have an account? Click here to sign in.

Having issues? You can contact us here

Accelerating Research