Search

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(n2k-5) instances of the minimum (⌊(k + √k)/2⌋ + 1)-way cut problem, and can be implemented to run in O(n4k/(1–1.71/√k)-31) time. With a slight modification, the algorithm can find all minimum k-way cuts in O(n4k/(1–1.71/√k)-16) time. [ABSTRACT FROM AUTHOR]

Details the development of tunable picosecond dye laser for multiphoton ionization of dioxin precursors in supersonic jet/time-of-flight mass spectrometry. More efficient ionization provided by the dye laser than that of the nanosecond laser used in supersonic jet spectrometry; Other advantages of picosecond over nanosecond and femtosecond lasers.

In the building block approach it is difficult to estimate the size of a circuit (a set of blocks) which can be implemented on a chip, based only on the areas of blocks and the chip area. Consequently, in the layout design by this approach, not only the area of each block, but also its shape and size must explicitly be taken into account. This paper discusses the placement of relatively small-sized blocks (I/O blocks) which realize the specified input-output function. The I/O block is assumed to have a rectangular shape, and some restriction is imposed on the edge lengths. In the placement of the I/O blocks, the given I/O blocks are converted into unit blocks with the standard sizes, and the placement is performed for the unit blocks. For the placement of unit blocks, the following results are obtained. For a set of unit blocks U and a set of rectangular regions I, the necessary and sufficient condition is derived for the existence of the placement of U on I. Then an algorithm is given which determines the placement for given U and I satisfying the condition in 0(∣U∣ + ∣I∣ log ∣I∣) time. [ABSTRACT FROM AUTHOR]

In the one-dimensional array approach, a logic circuit is realized by arranging NAND (NOR) gates in a one-dimensional array and interconnecting them. The horizontal length of the resultant layout of the logic circuit is determined uniquely by the number of given gates, while the vertical length varies depending on the order of assignment of gates. Thus, to minimize the area required, we must find a one-dimensional assignment of gates so as to minimize the vertical length. This optimization problem (called problem G) has been formulated as a graph problem and has already been proved to be NP-hard. In this paper, a restricted problem (called the problem R) is introduced anew wherein a connection of each net is restricted to be between two gates. The problem R plays an important role in developing a heuristic algorithm for the problem G. As for the time complexity, we show that the problem R is also NP-hard. [ABSTRACT FROM AUTHOR]

With the recent development of semiconductor integration technology, the amount of data that must be handled in the layout design of VLSI is increasing rapidly. Even if the improvement of the processing speed of the computer in the future is considered, it is desired to develop a high-speed layout algorithm compared to the conventional method. This paper discusses the k (> 2)-way graph partitioning problem, which is one of the most basic problems concerning the layout design. A parallel algorithm is proposed. The general method to solve this problem has been to apply hierarchically the two-way graph partitioning algorithm. In this method, the algorithm can easily be executed in parallel by operating a number of processors at each hierarchy. A problem then is the efficiency of the processor and the computation time. This paper considers the k-way graph partitioning and proposes a new method called nonhierarchical k-way graph partitioning, aiming at the education of the computation time by parallel processing. In general, it is considered difficult to improve the speed sufficiently by the parallel processing, while maintaining the same accuracy of the solution as that of the sequential algorithm. In this paper, the effectiveness of the proposed algorithm is shown by a simulation experiment on the sequential computer. [ABSTRACT FROM AUTHOR]

In VLSI layout design by the building block approach, a hierarchical floorplanning method is proposed in which the floorplan and global routing are determined simultaneously to realize low-congestion switchboxes. In this method, overlap resolution, which pre- serves relative position and minimizes the obtained chip area, is needed to prevent the increase in the wire length of each net. In this paper, a fundamental study of this overlap resolution Is made, and the following are described. (1) The formulation of the overlap resolution problem RI is given. In the formulation, (a) preservation of relative position among blocks, and (b) the minimization of obtained chip area are considered; (2) the computational complexity of the problem is analyzed, and then NP-completeness of the problem RI is proved; and (3) a polynomial heuristic algorithm R for the problem RI is given. In addition, the result of simulation experiments to verify the efficiency of the heuristic algorithm R is also described. [ABSTRACT FROM AUTHOR]

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 scheduling problem of meetings and presents a meeting scheduler for office automation which provides an automatic mechanism for updating a schedule of meetings. [ABSTRACT FROM AUTHOR]

In the detailed routing for VLSI standard cell layout design, the over-the-cell channel routing, which utilizes the over-the-cell region as the routing region, has been proposed. In this design method, after determining the net assignment to each channel in the global routing step, the track assignment both in channel and on over-the-cell regions is performed by an over-the-cell channel router. However, conventional global routing algorithms do not assume over-the-cell routing but conventional channel routing. Therefore, the minimization of channel density does not always successfully lead to the minimization of the final channel height. This paper presents a new global routing method for standard cell layouts to determine global routes for each net in both channel and over-the-cell regions simultaneously. The standard cell layout design system GLORIA based on the proposed algorithm is developed, and the experimental results compared with the conventional global routing method that performs the over-the-cell channel routing after global-routing with TimberWolf-SC4.2c are reported. Experimental results showed that the proposed routing algorithm can route about 18.4 percent fewer number of tracks than the conventional routing method, and the effectiveness of the proposed method is shown. The experimental results of applying the proposed method to the three-layer routing layout model also are presented. [ABSTRACT FROM AUTHOR]

In a VLSI layout design using the building block approach, design is divide into two phases, placement and routing. On the other hand, a new hierarchical floorplanning method was proposed by Dai et al., in which a global routing for the evaluation of the placement. However, the precise estimation of routability is difficult since the global routes in this method do not correspond to the routing region such as channels and switchboxes. In this paper, a new method is proposed, which simultaneously and hierarchically obtains floorplan, shapes and positions of modules, and global routes which directly correspond to switchboxes and channels. In this method, the routing-based partitioning, the hierarchical detailed global routing, and the hierarchical positioning are repeatedly executed, and a chip which small area and short wire length is obtained. This paper presents these three algorithms, and discusses the experimental results of each algorithm and the whole proposed method in a comparison to the conventional method that separately executes placement and routing. [ABSTRACT FROM AUTHOR]

This paper considers the building block method, which is one of the methods in VLSI layout design, and discusses the improvement of module placement assuming that a one-dimensional placement of the modules is given as the initial placement. Discussions are made of the following: (1) The case where net list given as the input is composed only of two-terminal nets, which connect the external terminals and the modules. The placement improvement problem PMO is formulated, Where the virtual connection length defined only by x coordinate is to be minimized while retaining the placement order of the modules. The algorithm to solve this problems as well as the proof for the optimality, are presented. Then a problem PM1 with a constraint on the range of displacement of the module is considered, and it is shown that the problem can be solved by extending the algorithm for PMO. (2) A problem PM2 is considered, which is am extension of PM1 by introducing in general the multiterminal net connecting modules and external terminals. It is shown that PM2 can be reduced to PM1. (3) A problem PM3 is considered, where river routing is adopted as the connection model, and the connection length is to be minimized considering also g coordinates (separation). It is shown that the optimal solution can be obtained in a polynomial time of the number of modules and the number of nets. [ABSTRACT FROM AUTHOR]

in VLSI layout design, the placement problem of functional blocks with different sizes and shapes include two NP-hard problems, that is, the problem of minimizing the chip size and the problem of minimizing the total virtual wire length. Therefore, in general, it is considered that any efficient placement method is very hard to develop. As a fundamental consideration of the placement problem, this paper discusses a placement problem in which the size of each block to be placed is restricted. First, the placement problem MSL in which the size of each block is restricted to be either 2 × 2, 2 × 1, or 1 × 1 is formulated. Next, a heuristic algorithm for the problem MSL is presented and some theoretical consideration on the proposed algorithm is given. In the theoretical consideration, the following two results are shown: 1) that the algorithm can find an initial placement with minimum chip area within a linear time on the number of blocks; and 2) that a set of placement change operations used to improve the total virtual wire length is a sufficient set of operations in a sense that any placement can always be transformed into another arbitrary placement by using the set of operations. Finally, the results of simulation experiment which was performed to evaluate empirically the proposed algorithm are scribed. [ABSTRACT FROM AUTHOR]

One of the interesting issues in the management of large computer networks is to partition the network into clusters and then to perform the management for each cluster. This paper presents a basic discussion on the initial clustering problem for a given network. The initial clustering problem C is defined as follows. Given a graphic representation G(V,E), V-n of a network and a set of nodes G-(c)1≤ r ≤ m) &epsive; 1, the graph G is to be partitioned into m connected subgraphs Gi = (Vi, Ei) (1≦i≦m) of G satisfying the following conditions: &o1; V, O C= (c), &o2; V, ≦K (a positive integer); and &o3; the distance between v&epsive; V, and Cx&epsive; C is minimum when x = i. The following results were obtained for the time complexity of the problem C: (1) the initial clustering problem C is in general NP-hard; and (2) the sub-problem obtained by deleting the condition &o2; can be solved in O(n⊃). [ABSTRACT FROM AUTHOR]