| On the implementation of MST-based heuristics for the Steiner problem in graphs (2002) | |||||||||||||||||
Abstract | |||||||||||||||||
| 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 ecient 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 signicantly, 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. 1 | |||||||||||||||||
Details der Publikation | |||||||||||||||||
| |||||||||||||||||