On the Implementation of MST-Based Heuristics for the Steiner Problem in Graphs

Some of the most widely used constructive heuristics for the Steiner Problem in Graphs are based on algorithms for the Minimum Spanning Tree problem. In this paper, we examine efficient implementations of heuristics based on the classic algorithms by Prim, Kruskal, and Borůvka. An extensive experimental study indicates that the theoretical worst-case complexity of the algorithms give little information about their behavior in practice. Careful implementation improves average computation times not only significantly, but asymptotically. Running times for our implementations are within a small constant factor from that of Prim’s algorithm for the Minimum Spanning Tree problem, suggesting that there is little room for improvement.