Minimum Moment Steiner Trees Conference Paper uri icon

abstract

  • For a rectilinear Steiner tree T with a root, define its k-th moment M k(T) = ∫ T(d T(u)) k du, where the integration is over all edges of T, d T(u) is the length of the unique path in T from the root to u, and du is the incremental edge length. Given a set of points P in the plane, a k-th moment Steiner Minimum Tree (k-SMT) is a rectilinear Steiner tree that has the minimum k-th moment among all rectilinear Steiner trees for P, with the origin as the root. The definition is a natural extension of the traditional Steiner minimum tree, and motivated by application in VLSI routing. In this paper properties of the k-SMT are studied and approximation algorithms are presented.

author list (cited authors)

  • Qiu, W., & Shi, W.

publication date

  • April 2004