Thumbnail
Access Restriction
Subscribed

Author Uchoa, Eduardo ♦ Werneck, Renato F.
Source ACM Digital Library
Content type Text
Publisher Association for Computing Machinery (ACM)
File Format PDF
Copyright Year ©2012
Language English
Subject Domain (in DDC) Computer science, information & general works ♦ Computer programming, programs & data
Subject Keyword Steiner trees ♦ Algorithms ♦ Data structures ♦ Experimental evaluation ♦ Heuristics ♦ Local search
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 good-quality solutions in practice, but high running times limited their applicability.
ISSN 10846654
Age Range 18 to 22 years ♦ above 22 year
Educational Use Research
Education Level UG and PG
Learning Resource Type Article
Publisher Date 2012-05-01
Publisher Place New York
e-ISSN 10846654
Journal Journal of Experimental Algorithmics (JEA)
Volume Number 17
Page Count 22
Starting Page 2.1
Ending Page 2.22


Open content in new tab

   Open content in new tab
Source: ACM Digital Library