ABSTRACT
This chapter addresses several variations of the corresponding fundamental Steiner minimal tree problem, where a given set of pins is to be connected using minimum total wirelength. It focuses on the corresponding classical objective of wirelength/area minimization and describes the general problem of minimum-cost Steiner tree construction in the presence of multiport terminals, where rather than spanning a set of nodes, the objective is to connect groups of nodes. A more general version of the Steiner problem arises when interpoint distances can be arbitrary, rather than induced by an underlying metric or a particular geometry. One version of the group Steiner problem, known as the strong-connectivity version, allows multiple connections to attach to different nodes in the same group. The group Steiner algorithm relies on depth-bounded trees. The degenerate groups by themselves induce an instance of the classic Steiner problem, and such an instance can be approximated efficiently with a constant performance ratio.
