AN ALGORITHM FOR STEINER TREES IN GRID GRAPHS AND ITS APPLICATION TO HOMOTOPIC ROUTING
Michael Kaufmann, Shaodi Gao, Krishnaiya Thulasiraman · Journal of Circuits Systems and Computers · 1996
In this paper we present an algorithm for Steiner minimal trees in grid graphs with all terminals located on the boundary of the graph. The algorithm runs in O(min{k4, k2n}) time, where k and n are the numbers of terminals and vertices of the graph, respectively. It can handle non-convex boundaries and is the fastest known for this case. We also consider the homotopic routing problem and apply our Steiner tree algorithm to construct minimum-length wires for multi-terminal nets.