A Linear Time Algorithm for Circular Permutation Layout.
dc.contributor.author | Rim, C.S. | en_US |
dc.contributor.author | Naclerio, N.J. | en_US |
dc.contributor.author | Masuda, Sumio | en_US |
dc.contributor.author | Nakajima, K. | en_US |
dc.contributor.department | ISR | en_US |
dc.date.accessioned | 2007-05-23T09:41:24Z | |
dc.date.available | 2007-05-23T09:41:24Z | |
dc.date.issued | 1988 | en_US |
dc.description.abstract | Suppose 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.extent | 988385 bytes | |
dc.format.mimetype | application/pdf | |
dc.identifier.uri | http://hdl.handle.net/1903/4775 | |
dc.language.iso | en_US | en_US |
dc.relation.ispartofseries | ISR; TR 1988-45 | en_US |
dc.title | A Linear Time Algorithm for Circular Permutation Layout. | en_US |
dc.type | Technical Report | en_US |
Files
Original bundle
1 - 1 of 1