For a given 2-edge-connected graph G and a spanning tree T of G, the graph augmentation problem 2ECA (T,G) is to find a minimum edge set AE (G) such that T A is 2-edge-connected. This note proves that 2ECA (T, G) is solvable in polynomial time if G is series-parallel.

A concept of metric is defined in the set of labelled graphs. The concept is based on the idea that the extent of the difference in two graphs may be measured by the non-orthogonality of tie-set (loop) vectors of one graph to the cut-set vectors of the other. The meanings involved in the concept are discussed on the topics concerning flow and tension networks. Applications to electrical networks include the theorem that, for a non-reciprocal n-port network N which is realized by using λN controlled-sources, an inequality 1/2 rank (YYT)D(gc, gv)λN holds where Y is the admittance matrix of N and D(gc, gv) is the distance between the corresponding current graph gc and voltage graph gv of N. An example for which the equalities hold in the above inequality is given.

In reuse of the VLSI layout design when technology migration takes place, the information to be abstracted from the original design and the data structure to store the information shall be specified. In this paper, they are assumed as the seg-based 4-direction and the parametric BSG, respectively. The parametric BSG is a BSG whose segs are generalized to take any number of units of length. The seg-based 4-direction is the right-of, left-of, above, and below relations between two rooms in accordance with the segs between them. An elegant procedure is given to map the floorplan of the model into a parametric BSG of the minimum size, keeping the abstracted seg-based 4-direction. Merits of the PBSG are discussed and a way of reuse is suggested by illustrative instances. Finally, a superior potential of the parametric BSG as the data structure is discussed empirically.

The most basic cross-talk minimization problem is to assign given n intervals to n parallel tracks where the cross-talk is defined between two intervals assigned to the adjacent tracks with the amount linear to parallel running length. This paper solves the problem for the case when any pair of intervals intersects and the objective is to minimize the sum of cross-talks. We begin the discussion with the fact that twice the sum of lengths of n/2 shortest intervals is a lower bound. Then an interval set that attains this lower bound is characterized with a simple assignment algorithm. Some additional considerations provide the minimum cross-talk for the other interval sets. The main procedure is to sort the intervals twice with respect to the length of left and right halves of intervals.

One of the difficulties in routing problem is in wirability which is to guarantee a physical connection of a given topological route. Wirability often fails since the width of a wire is relatively large compared with the size of modules. As a possible solution, this paper proposes an incremental wiring algorithm which generates wires net-by-net without overlapping other pre-placed circuit elements. The idea is to divide a wire into a series of rectangles and handles them as modules with additional constraints to keep the shape of the wire. The algorithm was implemented and experimented on a small instance to show its promising performance.

The family Pk of graphs with proper-path-width at most k is minor-closed. It is known that the number of minimal forbidden minors for a minor-closed family of graphs is finite, but we have few such families for which all the minimal forbidden minors are listed. Although the minimal acyclic forbidden minors are characterized for Pk, all the minimal forbidden minors are known only for P1. This paper lists 36 minimal forbidden minors for P2, and shows that there exist no other minimal forbidden minors for P2.

A graph G is said to be universal for a family F of graphs if G contains every graph in F as a subgraph. A minimum universal graph for F is a universal graph for F with the minimum number of edges. This paper considers a minimum universal graph for the family Fkn of graphs on n vertices with path-width at most k. We first show that the number of edges in a universal graph Fkn is at least Ω(kn log(n/k)). Next, we construct a universal graph for Fkn with O(kn log(n/k)) edges, and show that the number of edges in a minimum universal graph for Fkn is Θ(kn log(n/k)) .

It is known that the clock-period can be shorter than the maximum of signal-delays between registers if the clock arrival time to each register is properly scheduled. The algorithm to design an optimal clock-schedule was given. In this paper, we propose a clock-tree routing algorithm that realizes a given clock-schedule using the Elmore-delay model. Following the deferred-merge-embedding (DME) framework, the algorithm generates a topology of the clock-tree and simultaneously determines the locations and sizes of intermediate buffers. The experimental results showed that this method constructs a clock-tree with moderate wire length for a random layout of scheduled registers. Notably, the required wire length for a gentle layout of scheduled registers was shown to be almost equal to that of zero-skew clock-trees.

The three dimensional (3D) packing problem is to arrange given rectangular boxes in a rectangular box of the minimum volume without overlapping each other. As an approach, this paper introduces the system of three sequences of the box labels, the sequence-triple, to encode the topology of the 3D-packing. The topology is the system of relative relations in pairs of boxes such as right-of, above, front-of, etc. It will be proved that the sequence-triple represents the topology of the tractable 3D-packings which is a 3D-packing such that there is an order of the boxes along which all the boxes are extracted one by one in a certain fixed direction without disturbing other remaining boxes. The idea is extended to the system of five ordered sequences, the sequence-quintuple. A decoding rule is given by which any 3D-packing is represented. These coding systems are applied to design heuristic algorithms by simulated annealing which search the codes for better 3D-packings. Experimental results were very convincing its usefulness as automated packing algorithms.

The switch-block architecture of FPGAs is discussed to see a good balance between programmable-switch resources and routability. For the purpose, FPGAs are assumed to have certain extremal structures, whose switch-blocks consist of parallel or complete switch-sets where a switch-set is a set of switches between two sides of the switch-block. A polynomial time detailed-routing algorithm for a given global-routing is presented if the switch-block consists of two or less parallel switch-sets or three that form a cycle. For other FPGAs, the corresponding decision problem is proved to be -complete. A best compromise between switch resources and routability is offered.

We introduce the interval set of a graph G which is a representation of the proper-path-decomposition of G, and show a linear time algorithm to construct an optimal interval set for any tree T. It is shown that a proper-path-decomposition of T with optimal width can be obtained from an optimal interval set of T in O(n log n) time.

Given a switch-box, let C be a connection requirement. If there is a polynomial time algorithm (router) to complete C, C is said to be tractable by the algorithm. There have been proposed a number of switch-box routers but none that makes clear its tractable problems. We propose a switch-box router, or rather a principle, BOX-PEELER with a simple characterization of a class of tractable problems. BOX-PEELER is developed to be an underlying concept in switch-box routing as LEFT-EDGE method has been in 2-side channel routing.

A challenge to an automated layout of analog ICs starts with the insight into high quality placements crafted by experts. We observe first that matched devices or elemental functions such as input, output, amplifiers, etc are clustered. Second, devices in the same cluster are located faithfully to the drawn schema. Third, these two features are simultaneously fulfilled in a well-compacted placement. This paper proposes a novel device-level placement that simulates the above features based on Sequence-Pair. A slight modification of the meaning, say, of relation "A is left-of B" to relation "A is not right-of B" enlarges the freedom and allows a neater compaction of clusters allowing zigzag border curves. As the consequence, clusters are placed faithfully to relative position in the schema. We tested our algorithm for industrial instances and compared results with those by manual design. The results showed better features in performance figures than the those of manual designs by, on average, 13.5% and 21.2% with respect to the area and total net-length.

The success in topdown design of recent huge system LSIs is in a seamless transfer of the information resulted from the high level design to the lower level of floorplanning. For the purpose, we introduce a new concept abstract floorplan which is included in the output of high level design. From the abstract floorplan, the pillar blocks are derived which are critical sets of blocks that are expected to determine the width and height of the chip, named the frame. Since the frame and pillar blocks are obtained in the high level stage, they are useful to keep the consistency in the low level physical design if we apply optimization regarding them as constraints. Experiments to MCNC benchmarks showed that abstract floorplanning by pillar blocks output a placement faithful to the one physically optimized block placement with respect to the chip area and the wire-length.

A floorplan specifies the layout of modules in very large scale integration (VLSI) design, and a new code, called the EQ-sequence, for representing a floorplan is presented in this paper. The EQ-sequence is based on a Q-sequence. The EQ-sequence can preserve the adjacent relationships of rooms on a floorplan, but the Q-sequence cannot. The algorithms for encoding, moving and decoding of an EQ-sequence are introduced. With the EQ-sequence, we can check whether two modules abut each other on a floorplan. It has been proved that any floorplan of n rooms is uniquely encoded by an EQ-sequence and any EQ-sequence is uniquely decoded to a floorplan, both in O(n) time.

Lately, time-multiplexed I/Os for multi-device implementations (e.g., multi-FPGA systems), have come into practical use. They realize multiple I/O signal transmissions between two devices in one system clock cycle using one I/O wire between the devices and multiple I/O clock cycles. Though they ease the limitation of the number of I/O-pins of each device, the system clock period becomes much longer approximately in proprotion to the maximum number of multiplexed I/Os on a signal path. There is no conventional partitioning algorithm considering the effect of time-multiplexed I/Os directly. We introduce a new cost function for evaluating the suitability of a bipartition for multi-device implementations with time-multiplexed I/Os. We propose a performance-driven bipartitioning method VIOP which minimizes the value of the cost function. Our method VIOP combines three algorithms, such that i) min-cut partitioning, ii) coarse performance-driven partitioning, iii) fine performance-driven partitioning. For min-cut partitioning and coarse performance-driven partitioning, we employ a well-known conventional bipartitioning algorithms CLIP-FM and DUBA, respectively. For fine performance-driven partitioning for the final improvement of a partition, we propose a partitioning algorithm CAVP. By our method VIOP, the average cost was improved by 10.4% compared with the well-known algorithms.

In this paper, we propose an improved network-flow based multi-way circuit partitioning algorithm whose objective is to minimize the number of sub-circuits. It iteratively extracts a size-maximal feasible sub-circuit one at a time. In our approach, two devices are applied. One is in the use of an exact min-cut graph, and the other is in the idea of keeping the number of I/O pins of the residual circuit as small as possible after one-time extraction. We implemented our algorithm in C for experiments, and tested it with several industrial cases and MCNC benchmarks. Compared to the known approach, we observed more than 10% reduction in average of the sub-circuit number.

The most crucial factor that degrades a high speed VLSI is the signal propagation delay in a routing tree. It is estimated by the sum of the delay caused by the source-to-sink path length and by the total length. To design a routing tree in which these two are both small and balanced, we propose an algorithm to construct such a spanning tree, based on the idea of constructing a tree combining the minimum-spanning-tree and shortest-path-tree algorithms. This idea is extended to finding a rectilinear Steiner tree. Experiments are presented to illustrate how the source-to-sink path length and total length can be ballanced and small.

The shape-based routing needs a routing architecture with a geometrical computation framework on it. This paper introduces a novel routing architecture, Oct-Touched Tile (OTT), with a geometrical computation method along the horizontal- and vertical-constraints. The architecture is represented by the tiles spreading over the 2-D plane. Each tile is flexible to satisfy the constraints imposed for non-overlapping and sizing request. In this framework, path finding and shape-based sizing are executed on the same architecture. In experiments, our system demonstrates the performance comparable to a commercial tool. In addition, we show potential of OTT by introducing several ideas of extensions to analog layout constraints.