Present approximative algorithms for Steiner’s problem in graphs. Classification and two new fast approaches

The paper presents the Steiner problem, i.e. the minimum-cost-tree problem, relates it to the minimum spanning tree problem and the algorithms thereof, and then goes on to give two algorithms for the Steiner problem. First of these algorithms is derived from the multiple-component procedure of the generalized minimum spanning tree, and the second is related to the single component method of the ‘greedy’ procedure. Both of them are derived from the application of multiply rooted shortest path tree algorithms. That is also partly why both of the algorithms proposed have good time and space properties. These properties are then analysed on a sample of random graphs.