Approximating the Steiner Tree in the Placement Process
Y.- T. Wong and M. Pecht
By simulating the movement of a node in a tree, an iso-distance error
graph (IDEG) with its equivalent non-Steiner tree is developed. The
IDEG is used to estimate how well various types of non-Steiner trees function
as a Steiner tree in the placement of components on a printed wiring board
(PWB). To reduce connection errors in the IDEG and pursue computational
efficiency, a row-based tree family in which the tree length is primarily
dependent on the terminal coordinates of each row, is constructed.
Then, based on the analysis of the error distribution on the IDEG, the
row-based trees and the spanning tree are compared in terms of their approximation
to the Steiner tree.
article is available to CALCE Consortium Members.