ABSTRACT
The Steiner minimum tree problem, which asks for a minimum-length interconnection of a given set of terminals in the plane, is one of the fundamental problems in very large-scale integration (VLSI) physical design. Although advances in VLSI manufacturing technologies have introduced additional routing objectives, minimum length continues to be the primary objective when routing noncritical nets, since the minimum-length interconnection has minimum total capacitance and occupies minimum amount of area.
