A parallel genetic algorithm for the Steiner Problem in Networks

Downloads

[1] E. Cant-Paz, A summary of research on parallel genetic algorithms, Technical Report 950076, Illinois Genetic Algorithm Lab., Univ. Illinois Urbana- Champaign, Urbana, IL, July 1995. [2] G. Di Fatta, G. Lo Re, Efficient tree construction for the multicast problem, Special issue of the Journal of the Brazilian Telecommunications Society, 1999. [3] G. Di Fatta, G. Lo Presti, G. Lo Re, Computer Network Topologies: Models and Generation Tools, CE.R.E. Technical Report 5, July 2001. [4] K. A. Dowsland, Hill-climbing, Simulated Annealing and the Steiner Problem in Graphs, Engineering Optimisation, 17, 1991, pp. 91-107. [5] H. Esbensen, Computing Near-Optimal Solutions to the Steiner Problem in a Graph Using a Genetic Algorithm, Networks: An International Journal, 26, 1995. [6] M. Faloutsos, P. Faloutsos, C. Faloutsos, On Power- Law Relationships of the Internet Topology, ACM SIGCOMM, 1999. [7] M. Gendreau, J. F. Larochelle, B. Sanso, A Tabu Search Heuristic for the Steiner Tree Problem, Networks, 34, 1999, 162-172. [8] D. E. Goldberg, Genetic algorithm in Search, Optimization, and Machine Learning (Reading, MA: Addison Wesley, 1989). [9] R. Govindan, H. Tangmunarunkit, Heuristics for Internet Map Discovery, Proc IEEE Infocom 2000, Tel Aviv, Israel. [10] R. M. Karp, Reducibility among Combinatorial Problems, in R. E. Miller, J. W. Thatcher (Eds.), Complexity of Computer Computations (Plenum Press, New York, 1972, 85-103). [11] L. Kou, G. Markowsky, L. Berman, A fast algorithm for Steiner trees, Acta Inform., 15, 1981, 141-145. [12] J. Kruskal, On the Shortest Spanning Subtree of a Graph and the Traveling Salesman Problem, Proc. Amer. Math. Soc., 7, 1956, 48-50. [13] A. Medina, A. Lakhina, I. Matta, J. Byers, BRITE Universal Topology Generator, 2001, cs-pub.bu.edu/brite. [14] A. Medina, I. Matta, J. Byers, On the Origin of Power Laws in Internet Topologies, ACM SIGCOMM 2000, 30(2), April 2000. [15] Message Passing Interface Forum. MPI: A new message-passing interface standard (version 1.1), Technical Report, University of Tennessee, 1995. [16] V. J. Rayward-Smith, The computation of nearly minimal Steiner trees in graphs, Int. Math. Ed. Sci. Tech. 14, 1983, 15-23. [17] V. J. Rayward-Smith, A. Clare, On Finding Steiner Vertices, Networks, 16, 1986, 283-294. [18] H. Tangmunarunkit, R. Govindan, S. Jamin, et al., Network Topologies, Power Laws, and Hierarchy, SIGCOMM 2001, June 2001. [19] H. Takahashi, A Matsuyama, An approximate solution for the Steiner problem in graphs, Math. Japan, 1980, 573-577. [20] M. Tomassini, Parallel and distributed evolutionary algorithms: A review, in K. Miettinen, M. Mkel, P. Neittaanmki, J. Periaux, Evolutionary Algorithms in Engineering and Computer Science (Eds. New York: Wiley, 1999, 113-133). [21] S. Voss, A. Martin, T. Koch, SteinLib Testdata Library, February 2001, elib.zib.de/steinlib/steinlib.php. [22] P. Winter, Steiner problem in networks: a survey, Networks, 17, 1987, 129-167.