Browsing by Author "Nakajima, K."
Now showing 1 - 13 of 13
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 Circular-Arc Containment Graphs.(1988) Nirkhe, M.V.; Masuda, Sumio; Nakajima, K.; ISRWe introduce a new class of containment graphs called circular- arc containment graphs. A graph is called a circular-arc containment graph if there exists a family of arcs on a circle, such that each vertex corresponds to an arc and two vertices are connected by an edge if and only if one of the corresponding arcs contains the other. We characterize this class of graphs by establishing its equivalence to another relatively new class of intersection graphs, called circular permutation graphs. Given a circulararc containment graph in the form of a family of arcs on a circle, we describe efficient algorithms for finding a maximum clique and a maximum independent set of the graph.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 Efficient Algorithms for Finding Maximum Cliques of an Overlap Graph.(1986) Masuda, Sumio; Nakajima, K.; Kashiwabara, Toshinobu; Fujisawa, Toshio; ISRLet F = {I_1, I_2, ..., I_n} be a finite family of closed intervals on the real line. For two distinct intervals I_j and I_k in F, we say that I_j and I_k overlap with each other if they interact with each other but neither one of them contains the other. A graph G = (V, E) is called an overlap graph for F if there is a one-to-one correspondence between V and F such that two vertices in V are adjacent to each other if and only if the corresponding two intervals in F overlap with each other. In this paper, we present two efficient algorithms for finding maximum cliques of an overlap graph when the graph is given in the form of a family of intervals. The first algorithm finds a maximum clique in O time, where n , m are the numbers of vertices , edges, respectively, WEIRD GREEK LETTER is the size of a maximum clique of the graph. The second algorithm generates all maximum cliques of the graph in O time, where WEIRD GREEK LETTER is the total sum of the sizes of the maximum cliques.Item Efficient Enumeration of Maximal and Maximum Independent Sets of an Interval Graph and a Circular-Arc Graph.(1987) Masuda, Sumio; Nakajima, K.; Kashiwabara, Toshinobu; Fujisawa, Toshio; ISRWe present efficient algorithms for generating all maximal and all maximum independent sets of an interval graph and a circular- arc graph. When an interval graph is given in the form of a family of n intervals, the first and second algorithms produce all maximal and all maximum independent sets, respectively, in O(n DOT log n+ (the size of an output)) time. When a circular- arc graph is given in the form of a family of n arcs on a circle, the third algorithm generates all maximal independent sets in O(n log n+ (the size of an output)) time. In the same situation, the fourth algorithm enumerates all maximum independent aets in O(n^2+ (the size of an output)) time. The first three algorithms are optimal to within a constant factor.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 Generation of Maximum Independent Sets of a Biparite Graph and Maximum Cliques of a Circular-Arc Graph.(1989) Kashiwabara, Toshinobu; Masuda, Sumio; Nakajima, K.; Fujisawa, Toshio; ISRWe present an efflcient algorithm for generating all maximum independent sets of a bipartite graph. Its time complexity is O (n sup 2.5 + (output size )), where n is the number of vertices of a given graph. As its application, we develop an algorithm for generating all maximum cliques of a circular-arc graph. When the graph is given in the form of a family of n arcs on a circle, this algorithm runs in O ( n sup 3.5 + (output size )) time.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.Item An Optimal Algorithm for Finding a Maximum Independent Set of a Circular-Arc Graph.(1986) Masuda, Sumio; Nakajima, K.; ISRA new algorithm is presented for finding a maximum independent set of a circular-arc graph. When the graph is given in the form of a family of n arcs, our algorithm requires only O(n log n) time and O(n) space. Furthermore, if the endpoints of the arcs are already sorted, it runs in O(n) time. This algorithm is time- and space-optimal to within a constant factor.Item An Optimal Diagnosis Structure for Distributed Systems .(1989) Shih, F.H.W.; Nakajima, K.; ISRWe propose a simple structure which provides optimal system-level fault diagnosis. Each unit of a system can diagnose itself using test outcomes generated within its associated structure. This property makes the structure suitable for systems in a distributed environment where no central processor exists for fault diagnosis. We present a simple diagnosis algorithm based on this structure. Furthermore, we show that the proposed structure always exists for every unit in a system whose graph connectiviq is not less than the number of faulty units. We provide some examples of applying this unit-diagnosis approach to such systems as Boolean N-cube, generalized hypercube and DeBrujin networks. Distributed diagnosis can, therefore, be efficiently done for these fault-tolerant systems with results superior to those previously obtained.Item System Level Fault Diagnosis: An Overview.(1986) Narasimhan, J.; Nakajima, K.; ISRRecent times have seen a rapid growth in the development of digital systems. The cost of the hardware has shown a remarkable decline allowing designers to build systems which are extremely complex. This in turn has resulted in these complex systems being used in aplications which require a high degree of reliability. With the advent of a distributed processing environment a large number of quasi independent modules are now interconnected to form megasystems. The real time applications in which these systems are used require that their designee build into them efficient means of failure detection and in most cases correction mechanisms. Circuit level fault diagnosis , correction techniques are used widely in building digital systems. However the complexity , the interconnections of the various modules involved in the structure of these systems require fault diagnosis at a system level too. The importance of system level diagnosis has been recognized by many in the recent past , has encouraged a lot of research which has now reached quite an advanced stage.Item The Via Minimization Problem is NP-Complete.(1987) Naclerio, N.J.; Masuda, Sumio; Nakajima, K.; ISRVias between different layers of interconnection on dense integrated circuits tend to reduce yield, degrade performance, and take up a large amount of chip area. Similarly, contact holes on multilayer printed circuit boards add to manufacturing cost, and reduce reliability. Thus, many researchers have examined ways to minimize the number of vias required for a particular circuit layout. In this paper, we analyze the computational complexity of the so-called Constrained Via Minimization problem. Given an already routed circuit, the problem is to find a minimum cardinality set of vias for which a valid layer assignment exists. We first prove that the corresponding decision problem is NP-complete. We then show that it remains NP-complete even if one or more of the following restrictions are imposed.