On the implementation of MST-based heuristics for the Steiner problem in graphs, with M. Poggi de Aragão. Proceedings of the 4th Workshop on Algorithm Engineering and Experiments (ALENEX'02), San Francisco, Lecture Notes in Computer Science, volume 2409, pp. 1-15, Springer-Verlag, 2002. Copyright Springer-Verlag.

Abstract: 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 Boruvka. 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.