A Linear Time Algorithm for Circular Permutation Layout.

dc.contributor.authorRim, C.S.en_US
dc.contributor.authorNaclerio, N.J.en_US
dc.contributor.authorMasuda, Sumioen_US
dc.contributor.authorNakajima, K.en_US
dc.contributor.departmentISRen_US
dc.date.accessioned2007-05-23T09:41:24Z
dc.date.available2007-05-23T09:41:24Z
dc.date.issued1988en_US
dc.description.abstractSuppose that two sets of terminals t_l,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 which 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) at most one wire can pass between any two adjacent terminals on C_in, and (iii) no wire can cross C_in more than once. The previously known algorithm for the same case has time complexity O(n^2).en_US
dc.format.extent988385 bytes
dc.format.mimetypeapplication/pdf
dc.identifier.urihttp://hdl.handle.net/1903/4775
dc.language.isoen_USen_US
dc.relation.ispartofseriesISR; TR 1988-45en_US
dc.titleA Linear Time Algorithm for Circular Permutation Layout.en_US
dc.typeTechnical Reporten_US

Files

Original bundle
Now showing 1 - 1 of 1
Loading...
Thumbnail Image
Name:
TR_88-45.pdf
Size:
965.22 KB
Format:
Adobe Portable Document Format