The building blocks in a given floorplan have several possible physical implementations yielding different layouts. A discussion is presented of the problem of selecting an optimal implementation for each building block so that the area of the final layout is minimized. A polynomial algorithm that solves this problem for slicing floorplans was presented elsewhere, and it has been proved that for general (nonslicing) floorplans the problem is NP-complete. The authors suggest a branch-and-bound algorithm which proves to be very efficient and can handle successfully large general nonslicing floorplans. The high efficiency of the algorithm stems from the branching strategy and the bounding function used in the search procedure. The branch-and-bound algorithm is supplemented by a heuristic minimization procedure which further prunes the search, is computationally efficient, and does not prevent achieving a global minimum. Finally, the authors show how the nonslicing and the slicing algorithms can be combined to handle efficiently very large general floorplans.>

This paper describes a procedure for a suboptimal routing of simultaneous multiterminal multicommodity flows in circuit switched communication networks. The procedure is based on a concept of topological importance of a branch in a capacitated net with a given structure and relative to a given pattern of communication requirements. Once these importance weights have been attached to the branches of the net, the problem reduces to finding in a weighted network the shortest path between two nodes. The chosen objective here is to optimize the grade of service (GS) by satisfying (on a long-range traffic policy basis) the changing "call" demands presented to the network, as fully as possible.

A Monte Carlo simulation program that enables the evaluation of different routing policies in a communication network is described. This simulation is intended to deal with nonoriented (telephone) networks and the grade of service (G/S) is taken as the performance measure. However, it can easily be adapted to deal with oriented or mixed networks. The program assigns to each branch of the analyzed network a price function. For each call, the route of minimal cost, among all available under the present load conditions in the network, is then chosen. The program was used for comparing routing policies, as initiated by different price functions. The comparisons were made on several test networks and for different traffic loads. The results obtained showed a significant improvement in the G/S for the policy that aimed at distributing the flow through the network in the most homogenous way possible. This homogenous flow distribution was obtained by using the above minimal-cost policy and a price function, assigned to each channel, that monotonically increases with the traffic load of the branch to which the particular channel belongs. The influence of the topological configuration of the network on the G/S, under equal external demands, was also investigated and the results are given. The way in which the results are printed out enables the simulation program to serve also as a practical and useful tool in the design (or the redesign) of a communication net.

In this paper some properties of unimodular (orE-) and paramount (orM-) matrices are discussed. The paper deals with matricesKwhich may be decomposed in a congruenceADA \primewhereAis a rectangular unimodular- andDa diagonal- matrix with constant, positive and real diagonal elements. It is shown that such a decomposition, if at all possible, is essentially unique and a direct algebraic procedure is given which results either in finding the pair of matricesAandDor in a proof that such decomposition is impossible. Since the admittance matrices ofn-ports described on pure resistance networks (or RLC networks for positive, real values of the complex frequency) withn + 1nodes, or dually the impedance matrices ofn-ports inscribed intoR-networks with exactlynindependent links belong to the Class ofADA \primematrices the paper defines a method of decomposition of such matrices into the productADA. The synthesis of the correspondingn-port may then be realized by known methods.