ABSTRACT
The goal of placement and routing is to provide the most effective connection of signals among devices, whether they are transistors on a chip or integrated circuits or modules on a printed circuit or wiring board. For these planar architectures, the approach to the connection of signals will determine the effectiveness of the placement and routing algorithms. The terminal locations of a signal set represent nodes or vertices in graph theory. An edge can be formed between any two known nodes or extra vertices. In a tree, edges are not allowed to form any cycles. The most common interconnection norm is the total wire or routing length. For a given node configuration, the length of a minimum source-sink tree is equal to or longer than that of a minimum spanning tree; the number of alternative source-sink trees of the same length as the minimum spanning tree is equal to or less than the number of alternative minimum spanning trees.
