M. Borah et al., AN EDGE-BASED HEURISTIC FOR STEINER ROUTING, IEEE transactions on computer-aided design of integrated circuits and systems, 13(12), 1994, pp. 1563-1568
A new approximation heuristic for finding a rectilinear Steiner tree o
f a set of nodes is presented. It starts with a rectilinear minium spa
nning tree of the nodes and repeatedly connects a node to the nearest
point on the rectangular layout of an edge, removing the longest edge
of the loop thus formed. A simple implementation of the heuristic usin
g conventional data structures is compared with previously existing al
gorithms. The performance (i.e., quality of the route produced) or our
algorithm is as good as the best reported algorithm, while the runnin
g time is an order of magnitude better than that of this best algorith
m. It is also shown that the asymptotic time complexity for the algori
thm can be improved to O(n log n), where n is the number of points in
the set.