A Hybrid GRASP with Perturbations for the Steiner Problem in Graphs

References

• Bastos M. P., Ribeiro C. C., Ribeiro C. C., Hansen P. Reactive tabu search with path-relinking for the Steiner problem in graphs. Essays and Surveys in Metaheuristics (2001) (Kluwer, Boston, MA) 39–58Google Scholar
• Beasley J. E. OR-Library: Distributing test problems by electronic mail. Journal of the Operational Research Society (1990) 41:1069–1072Crossref, Google Scholar
• Canuto S. A., Resende M. G. C., Ribeiro C. C. Local search with perturbations for the prize-collecting Steiner tree problem. Networks (2001) 38:50–58Crossref, Google Scholar
• Charon I., Hudry O. The noising method: a new method for combinatorial optimization. Operations Research Letters (1993) 14:133–137Crossref, Google Scholar
• Cormen T., Leiserson C., Rivest R.Introduction to Algorithms (1990) (MIT Press, Cambridge, MA) Google Scholar
• Dijkstra E. W. A note on two problems in connexion with graphs. Numerische Mathematik (1959) 1:269–271Crossref, Google Scholar
• Duin C. W.Steiner's Problem in Graphs: Approximation, Reduction, Variation (1994) (Doctorate Dissertation,Institute of Actuarial Science and Economics, University of Amsterdam, Amsterdam, The Netherlands) Google Scholar
• Duin C. W. (2001) . Personal communicationGoogle Scholar
• Duin C. W., Volgenant A. Reduction tests for the Steiner problem in graphs. Networks (1989) 19:549–567Crossref, Google Scholar
• Duin C. W., Voss S. Efficient path and vertex exchange in Steiner tree algorithms. Networks (1997) 29:89–105Crossref, Google Scholar
• Duin C. W., Voss S. The Pilot method: a strategy for heuristic repetition with application to the Steiner problem in graphs. Networks (1999) 34:181–191Crossref, Google Scholar
• Feo T. A., Resende M. G. Greedy randomized adaptive search procedures. Journal of Global Optimization (1995) 6:109–133Crossref, Google Scholar
• Fleurent C., Glover F. Improved constructive multistart strategies for the quadratic assignment problem using adaptive memory. INFORMS Journal on Computing (1999) 11:198–204Link, Google Scholar
• Gendreau M., Larochelle J.-F., Sansó B. A tabu search heuristic for the Steiner tree problem. Networks (1999) 34:163–172Crossref, Google Scholar
• Glover F., Barr R. S., Helga-son R. V., Kennington J. L. Tabu search and adaptive memory programing-advances, applications and challenges. Interfaces in Computer Science and Operations Research (1996) (Kluwer, Boston, MA) 1–75Google Scholar
• Glover F., Laguna M., onzáles-Velarde J. L. Multi-start and strategic oscillation methods-Principles to exploit adaptive memory. Computing Tools for Modeling, Optimization and Simulation: Interfaces in Computer Science and Operations Research (2000) (Kluwer, Boston, MA) 1–24Crossref, Google Scholar
• Glover F., Laguna M., Martí R. Fundamentals of scatter search and path relinking. Control and Cybernetics (2000) 39:653–684Google Scholar
• Hwang F. K., Richards D.S., Winter P.The Steiner Tree Problem (1992) (North-Holland, Amsterdam, The Netherlands) Google Scholar
• Karp R. M., Miller E., Thatcher J. W. Reducibility among combinatorial problems. Complexity of Computer Computations (1972) (Plenum Press, New York) 85–103Crossref, Google Scholar
• Koch T., Martin A. Solving Steiner tree problems in graphs to optimality. Networks (1998) 32:207–232Crossref, Google Scholar
• Koch T., Martin A., Voss S. SteinLib: an updated library on Steiner tree problems in graphs. (2001) . ZIB-Report 00-37, Konrad-Zuse-Zentrum für Informationstechnik Berlin,Berlin,Germany. Online document at http://elib.zib.de/steinlib/steinlib.html, acessed May 1, 2001Google Scholar
• Kruskal J. B. On the shortest spanning tree of a graph and he traveling salesman problem. Proceedings of the American Mathematical Society (1956) 7:48–50Crossref, Google Scholar
• Maculan N., Martello S., Laporte G., Minoux M., Ribeiro C. C. The Steiner problem in graphs. Annals of Discrete Mathematics 31: Surveys in Combinatorial Optimization (1987) (Elsevier, Amsterdam, The Netherlands) 185–212Crossref, Google Scholar
• Martins S. L., Pardalos P., Resende M. G., Ribeiro C. C. A parallel GRASP for the Steiner tree problem in graphs using a hybrid local search strategy. Journal of Global Optimization (2000) 17:267–283Crossref, Google Scholar
• Minoux M. Efficient greedy heuristics for Steiner tree problems using reoptimization and supermodularity. INFOR (1990) 28:221–233Google Scholar
• Poggi de Aragão M. V., Uchoa E., Werneck R. F. Dual heuristics on the exact solution of large Steiner problems. Electronic Notes in Discrete Mathematics (2001) 7Online document at http://www.elsevier.nl/locate/endmaccessed November 1, 2001Google Scholar
• Polzin T., Vahdati S. Improved algorithms for the Steiner problem in networks. Discrete Applied Mathematics (2001) 112:263–300Crossref, Google Scholar
• Ribeiro C. C., Souza M. C. Tabu search for the Steiner problem in graphs. Networks (2000) 36:138–146Crossref, Google Scholar
• Ribeiro C. C., Uchoa E., Werneck R. F. Computational results for algorithm HGP+PR. (2001) . Online document at http://www.inf.puc-rio.br/~celso/artigos/tabs-hgppr.ps, accessed November 1, 2001Google Scholar
• Takahashi H., Matsuyama A. An approximate solution for the Steiner problem in graphs. Math. Japonica (1980) 24:573–577Google Scholar
• Uchoa E., Poggi de Aragão M. V., Ribeiro C. C. Preprocessing Steiner problems from VLSI layout. (1999) . Monogra fias em Ciência da Computaçã;o 32/99,Department of Computer Science, Catholic University of Rio de Janeiro, Rio de Janeiro, BrazilGoogle Scholar
• Verhoeven M. G. A., Severens M. E. M., Aarts E. H. L., Rayward-Smith V. J., Osman I. H., Reeves C. R., Smith G. D. Local search for Steiner trees in graphs. Morden Heuristics Search Methods (1996) (Wiley, New York) 117–129Google Scholar
• Voss S.Steiner-Probleme in Graphen (1990) (Anton Hain, Frankfurt, Germany) Google Scholar
• Voss S. Steiner's problem in graphs: heuristic methods. Discrete Applied Mathematics (1992) 40:45–72Crossref, Google Scholar
• Winter P. Steiner problem in networks:a survey. Networks (1987) 17:129–167Crossref, Google Scholar
• Winter P. Reductions for the rectilinear Steiner tree problem. Networks (1995) 26:187–198Crossref, Google Scholar