Portal de Periódicos da CAPES

Capítulo de livro Produção Nacional Revisado por pares

BIBTEX RIS

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

2002; Springer Science+Business Media; Linguagem: Inglês

10.1007/3-540-45643-0_1

1611-3349

Marcus Poggi de Aragão, Renato F. Werneck,

Constraint Satisfaction and Optimization

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.