Efficient steiner tree construction based on spanning graphs

Steiner Minimal Tree (SMT) problem is a very important problem in VLSI CAD. Given n points on a plane, a Steiner minimal tree connects these points through some extra points (called Steiner points) to achieve a minimal total length. Even though there exist many heuristic algorithms for this problem, they have either poor performances or expensive running times. This paper records an implementation of an efficient Steiner minimal tree algorithm that has a worst case running time of O(n log n) and a similar performance as the Iterated 1-Steiner algorithm. The algorithm efficiently combines Borah et al.'s edge substitute concept with Zhou et al.'s spanning graph. Extensive experimental studies are conducted to compare it with other programs.