dollarasfen.blogg.se

12th Annual ACM Symposium on the Theory of Computing, 1980, 177–189 Google Scholar Patterson, Optimal tree layout (preliminary version), Proc. West, Automated circuit card etching layout, Proc. Donath, Complexity theory and design automation, Proc.17th Design Autom. Bryant, Third Caltech Conference on VLSI, Springer-Verlag, Berlin, 1983 Crossref Google Scholar

1: Theory and Techniques, Prentice-Hall, Englewood Cliffs, NJ, 1972 Google Scholar Breuer, Design Automation of Digital Systems, Vol.

Molitor, Ein CAD-System zum Entwurf integrierter Schaltungen, Technical Report, 16/1984, SFB 124 B1, Universität des Saarlandes, Saarbrücken, 1984 Google Scholar Osthof, Layouts with wires of balanced length STACS 85 (Saarbrücken, 1985), Lecture Notes in Comput. Becker, Masters Thesis, Über die kreuzungsfreie, rechtwinklige Einbettung von gewichteten Graphen in die Ebene, Ph.D, dissertation, Universität des Saarlandes, Saarbrücken, 1982 Google Scholar

In the Appendix we outline some (efficient, polynomial time) methods for the construction of optimal layouts and give as an example the optimal layouts of a recursively defined n-bit adder and multiplier. Our theorems show that no new contacts (crossing points) will be generated. We get an interesting characterization of nonplanar layouts of planar graphs, which shows that the optimal layout of a planar graph is planar or at least “quasiplanar.” This property makes it possible to decompose the general layout problem into two independent problems: (i) Find a layout of a circuit that is not necessarily planar, but that has an “lallowed crossing behaviour.” (ii) Fix the crossing points and then optimize the layout. The main part of the paper is concerned with planar graphs. The investigated layouts are straight line embeddings in a continuous part of the plane the cost of a layout is calculated with help of very general cost functions including the pth power of the usual Euclidean distance metric for $p = 2,3, \cdots $ (for short, $l_p $-metric).įor a large class of graphs, which, for example, occur in chip layout problems as the abstract structure of switching circuits, we show the existence and uniqueness of the optimal layout. In this paper we consider the (optimal) layout of graphs with fixed boundary (i.e., graphs, where only the nodes of a given cycle of the graph have fixed positions in the plane). Find a library where document is available.The optimal planar layout of planar graphs with respect to the $L_1 $- or $L_2 $-metric leads to NP-hard problems, if one assumes the nodes of the graph to be fixed in the plane (see, ).The validity of these algorithms is proven by academic examples, and the algorithms are then applied to the Munich subway tunnel project. Based on these understandings of the problem, 2 algorithms are proposed as a means of automatically generating the optimal measurements. The existence, uniqueness, and stability of the solution from the parameter identification process are thoroughly discussed. This paper focuses on designing the optimal measurement layout for parameter identification problems in geomechanics, which are usually based on in situ displacements. OPTIMAL LAYOUT OF DISPLACEMENT MEASUREMENTS FOR PARAMETER IDENTIFICATION PROCESS IN GEOMECHANICS