Fast Local Search for Steiner Trees in Graphs

Eduardo Uchoa and Renato F. Werneck

Abstract

We present efficient algorithms that implement four local searches for the Steiner problem in graphs: vertex insertion, vertex elimination, key-path exchange, and key-vertex elimination. In each case, we show how to find an improving solution (or prove that none exists in the neighborhood) in O(m log n) time on graphs with n vertices and m edges. Many of the techniques and data structures we use are relevant in the study of dynamic

graphs in general, beyond Steiner trees. Besides the theoretical interest, our results have practical impact: these local searches have been shown to find goodquality

solutions in practice, but high running times limited their applicability.

Details

Publication typeInproceedings
Published inProceedings of the 12th Workshop on Algorithm Engineering and Experiments (ALENEX)
URLhttp://www.siam.org/proceedings/alenex/2010/alx10_001_uchoae.pdf
Pages1-10
PublisherSociety for Industrial and Applied Mathematics
> Publications > Fast Local Search for Steiner Trees in Graphs