Browsing by Author "Kashiwabara, Toshinobu"
Now showing 1 - 7 of 7
Results Per Page
Sort Options
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 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 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 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.