A linear time algorithm for full Steiner trees.
01 January 1986
Full Steiner trees are building blocks for the construction of Steiner minimal trees. Melzak gave an elegant construction for full Steiner trees. However no polynomial time implementation of Melzak's construction was previously known. In this paper we show how it can be implemented to run in linear time.