An exact algorithm for the steiner tree might look like the one given in this paper:
"An Exact Algorithm for the Uniformly-Oriented Steiner Tree Problem" Benny K. Nielsen, Pawel Winter, and Martin Zachariasen http://www.springerlink.com/(ilim4245kwp0q545vzj1b345)/app/home/content.asp?referrer=contribution&format=2&page=1&pagecount=0 According to the abstract of the text, the algorithm is not useless, solving (easy?)instances with 10k 'teminals' optimally. The general 'steiner tree problem' is np-complete, meaning there is no known polynomial-time algorithm to solve it. (see wikipedia) -A way to generate approximations is by creating the minimum spanning tree of the vertices. (using the euclidian distance as cost). this can be done in time O(n ln n) with n the number of vertices. This guarantees to find solutions not more than 15.5% longer than needed. (see "the Algorithm Design Manual" Steven S Skiena, I think this text is available on the net somewhere too) --~--~---------~--~----~------------~-------~--~----~ You received this message because you are subscribed to the Google Groups "Algorithm Geeks" group. To post to this group, send email to algogeeks@googlegroups.com To unsubscribe from this group, send email to [EMAIL PROTECTED] For more options, visit this group at http://groups.google.com/group/algogeeks -~----------~----~----~----~------~----~------~--~---
