Let $G=(V,E)$ be an edge‐weighted undirected graph with n vertices and m edges. We present a deterministic algorithm to compute a minimum k‐way cut of G for a given k. Our algorithm is a divide‐and‐conquer method based on a procedure that reduces an instance of the minimum k‐way cut problem to $O(n^{2k-5})$ instances of the minimum $(\lfloor (k+\sqrt{k})/2\rfloor+1)$‐way cut problem, and can be implemented to run in $O(n^{4k/(1-1.71/\sqrt{k}) -31} )$ time. With a slight modification, the algorithm can find all minimum k‐way cuts in $O(n^{4k/(1-1.71/\sqrt{k}) -16} )$ time.

In this paper, we will consider global routing and pin assignment in VLSI building block layout, and present an efficient algorithm which integrates global routing, pin assignment, block reshaping and positioning. The general flow of the proposed algorithm is the same as the one proposed in by Cong in 1991 [1] and consists of two main phases. The first phase is to determine not only global routes and coarse pin assignment in the same way as [1], but also shapes and positions of blocks. The second phase is to compute the final pin assignment for channels. We generalize the channel pin assignment (CPA) problem in [1], in which the CPA problem is formulated for only channels formed by two blocks, to the CPA problem for channels formed by multiple blocks. We will propose a linear time optimal channel pin assignment algorithm, which is an extension of the algorithm in [1]. Experimental results show the effectiveness of the proposed algorithm.

No abstract available.

No abstract available.

This paper presents an MCM routing algorithm considering crosstalk. The aim of the algorithm is to minimize the total wire length under the condition that the crosstalk constraints among nets are satisfied. Experimental results show the effectiveness of the algorithm.

In this paper, we present a formal verification method based on internal variables of a given circuit. In this method, the problem of deciding the logical equivalence of two logic circuits is transformed to the satisfiability problem, which is solved by constructing a set of BDDs, each of which is corresponding to an internal variable of the circuit. Experimental results showed the effectiveness of the proposed method.

Given an undirected graph G with n vertices, m edges and positive edge weights and k terminals {s/sub 1/, s/sub 2/, ..., s/sub k/} on G, the problem of computing a minimum k-way cut of G is to find a minimum (cost) k-way cut C that disconnects each terminal from all the others. The minimum k-way cut problem is known as NP-hard even if all vertex degrees are three or less and k is equal to 3. The minimum k-way cut problem for a planar graph and fixed integer k can be solved in polynomial time. This paper presents an algorithm for computing a minimum three-way cut of a graph in a larger class than planar graphs.>

In this paper, we propose a heuristic floorplanning method. It is based on tentative insertion of constraints, that intentionally produces redundant constraints to make it possible to search in a wide range of solution space. The proposed method reduces the total area of blocks with the removal and insertion of constraints on the critical path in both horizontal and vertical constraint graphs. Experimental results showed that the quality of solutions of the proposed method is good and even for the large number of blocks, the proposed method keeps a high quality of solution.>

The graph partitioning problem is to partition the vertices of an undirected graph G=(V, E) into two sets of equal size such that the number of edges between them is minimized. In this paper, we propose a systolic algorithm for graph partitioning. The algorithm is based on the Kernighan-Lin heuristic algorithm, runs on a linear array consisting of O(|V|) processing units, and is very suitable for direct VLSI implementation. Computation time of one pass of the proposed algorithm is O(|V|). Simulation experiments showed that the proposed algorithm is as good as the original KL heuristic.>

Scheduling of meetings is one of the basic functions demanded in office automation, since office workers spend much time on meetings. This paper discusses a schedufkng problem of meetings and presents a meeting scheduler for office automation which provides an automatic mechanism for updating a schedule of meetings.

In this paper, we present a new approach for the one-dimensional gate assignment problem. The original minimization problem is transformed into a restricted problem, and then a new heuristic algorithm is applied to it. The solution obtained by the algorithm is interpreted as a solution for the original problem. The whole process of the approach has been implemented and tested with various examples. Experimental results show that our approach can approximately produce optimum solutions.

This paper attempts to design a user-friendly interface which enhances usability of relational database systems. Our approach to usability is to design a semantic data model suitable for a user interface and provide an easy-to-use query language DOMCALC (domain calculus language) which is based on the semantic data model. A query in DOMCALC can be described in terms of intuitive notions, namely domains, instead of relations and attributes. That is, DOMCALC requires for users no knowledge of a conceptual database such as relation names and attribute names. Therefore, the usability based on the semantic data model removes the requirement of knowledge of a conceptual database from users and protects user views from changes in the conceptual database. We also describe an outline of a database system PRIM (Prototype of Laboratory information Management System) which has been developed with the above considerations. This is a step toward the enhancement of usability in relational database systems.

The process of visiting a mini mal number of nodes to retrieve data satisfying the range condition from a binary search tree is called "selective traversal". Driscall and Lien gave an algorithm SELECT for selective traversal which used a MARKER field of 3 bits for each node in the tree. In this paper we present a new algorithm, called INPROC, which uses a MARKER field of 2 bits and runs faster than algorithm SELECT.