This paper describes an automatic/interactive layout design system for designing master-slice LSI chips, which places function blocks and gives wiring patterns on the chip. Since 100% routing is essential for master-slice layout design, it is urgently required to establish a strong CAD system, which significantly reduces the design time. The LAMBDA system has been developed to achieve complete net connectivity in as short a design time as possible, where efficient automatic procedures are implemented as well as highly interactive functions. The system adopts two-level hierarchy algorithms for placement and routing problems. Highly interactive functions are realized by exploiting human intelligence and the computer's high speed processing.

A series-parallel graph can be constructed from a certain graph by recurslvely applying "series" and "parallel" connections The class of such graphs, which Is a well-known model of series-parallel electrical networks, is a subclass of planar graphs It is shown in a umfied manner that there exist hnearume algorithms for many combinatorial problems ff an input graph is restricted to the class of series-parallel graphs.These include 0) the decision problem with respect to a property characterized by a finite number of forbidden graphs, (u) the mlmmum edge (vertex) deletion problem with respect to the same property as above, and (Ul) the generalized matching problem Consequently, the following problems, among others, prove to be hnear-tlme computable for the class of series-parallel graphs.(I) the minimum vertex cover problem, (2) the maximum outerplanar (reduced) subgraph problem, (3) the minimum feedback vertex set problem, (4) the maximum (induced) hne-subgraph problem, (5) the maximum matching problem, and (6) the maximum disjoint triangle problem.

Abstract A Hamiltonian walk of a graph is a closed spanning walk of minimum length. In this paper we generalize a Dirac type sufficient condition ensuring the existence of a Hamiltonian cycle to one ensuring the existence of a closed spanning walk of length less than a specified value. Furthermore, we present an O (p2 log p) algorithm for finding such a closed spanning walk in a graph with p vertices satisfying our condition.