Browsing by Author "Masuda, Sumio"
Now showing 1 - 10 of 10
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 Crossing Minimization in the Straight-Line Embedding of Graphs.(1987) Masuda, Sumio; Nakajima, Kazuo; Kashiwabara, Toshinobu; Fujisawa, Toshio; ISRThe problem of embedding a graph in the plane with the minimum number of edgecrossings arises in some circuit layout problems. It has been known that this problem is in general NP-hard. An interesting and relevant problem in the area of book embedding was recently shown to be NP-hard. This result implies that the former problem is NP-hard even when the vertices are placed on a straight line l and the edges are drawn completely on either side of l. In this paper, we show that the problem remains NP-hard even if, in addition to these constraints, the positions of the vertices on SCRIPT l are predetermined.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 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 An NP-Hard Crossing Minimization Problem for Computer Network Layout.(1986) Masuda, Sumio; Kashiwabara, Toshinobu; Nakajima, Kazuo; Fujisawa, Toshio; ISRA layout problem of computer communication network is formulated graph-theoretically as follows: "Given a simple graph G = (V,E), find an embedding of G with the minimum number of edge-crossings such that (i) the vertices in V are placed on the circumference of a circle C, and (ii) the edges in E are drawn only inside C." In this paper, this problem will be shown to be NP-hard. Therefore, it is very likely to be intractable.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 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.