Show simple item record

Circular Permutation Layout with Prescribed Between-Pin Congestions.

dc.contributor.authorRim, C.S.en_US
dc.contributor.authorMasuda, Sumioen_US
dc.contributor.authorNakajima, K.en_US
dc.description.abstractSuppose that two sets of terminals t_1,t_2, ..., t_n and b_1, b_2, ... ,b_n are located on two concentric circles C_out and C_in, respectively. Given a permutation PI of integers 1, 2, ..., n, the circular permutation layout problem is the problem of connecting each pair of terminals t_i and b_PI(i) for i = 1, 2, ..., n with zero width wires in such a way that no two wires that correspond to different terminal pairs intersect each other. In this paper, we present a linear time algorithm for the following case: (i) no wire can cross C_out, (ii) a wire can cross C_in at most once, and (iii) the number of wires which can pass between each pair of adjacent terminals on C_in is prespecified.en_US
dc.format.extent1430518 bytes
dc.relation.ispartofseriesISR; TR 1989-20en_US
dc.titleCircular Permutation Layout with Prescribed Between-Pin Congestions.en_US
dc.typeTechnical Reporten_US

Files in this item


This item appears in the following Collection(s)

Show simple item record