### Browsing by Author "Rim, C.S."

Now showing 1 - 5 of 5

###### Results Per Page

###### Sort Options

Item Circular Permutation Layout with Prescribed Between-Pin Congestions.(1989) Rim, C.S.; Masuda, Sumio; Nakajima, K.; ISRSuppose 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.Item Complexity Results for Rectangle Intersection and Overlap Graphs.(1988) Rim, C.S.; Nakajima, K.; ISRLet R be a family of iso-oriented rectangles in the plane. A graph G = (V, E) is called a rectangle intersection (resp., overlap) graph for R if there is a one-to-one correspondence between V and R such that two vertices in V are adjacent to each other if and only if the corresponding rectangles in R intersect (resp., overlap) each other. It is known that the maximum clique and minimum vertex coloring problems are solvable in polynomial time and NP-hard, respectively, for rectangle intersection graphs. In this paper, we first prove that maximum independent set problem is NP-hard even for both cubic planar rectangle intersection and cubic planar rectangle overlap graphs. We then show the NP-completeness of the vertex coloring problem with three colors for both planar rectangle intersection and planar rectangle overlap graphs even when the degree of every vertex is limited to four. Finally we described how to find, in polynomial time, a maximum clique of a rectangle overlap graph.Item Exact Algorithms for Multilayer Topological Via Minimization.(1988) Rim, C.S.; Kashiwabara, Toshinobu; Nakajima, K.; ISRWe consider the topological via minimization problem in which each of n nets has two terminals to be connected and the routing area consists of k layers. We first show that this problem is solvable in O(kn^2) time, using a minimum cost network flow algorithm, for the usual channel routing case in which no local net exists. We then consider the problem for the case of "circular" channel routing in which no local net exists, and present an O(n^(2k+1)) time algorithm using dynamic programming.Item A Linear Time Algorithm for Circular Permutation Layout.(1988) Rim, C.S.; Naclerio, N.J.; Masuda, Sumio; Nakajima, K.; ISRSuppose 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).Item A Note on the NP-hardness of the Topological Via Minimization Problem.(1989) Rim, C.S.; Kashiwabara, Toshinobu; Nakajima, K.; ISRSuppose that we are given a two-layer routing area bounded by a closed continuous curve B, a set of terminals placed on B which are available on both layers, and a set of two terminal-nets. The topological via minimization problem is the problem of routing the nets by zero-width wires such that no two wires corresponding to different nets intersect on the same layer and the number of vies used is minimized. Very recently, it was reported that this problem is NP-hard but the proof contains a critical flaw. In this paper, we present a correct NP-hardness proof of the problem.