GRASP bibliography: Graph theoretic applications

1. Scatter search for a network design problem

   A.M. Álvarez, J. L. González, and K. De-Alba

   Technical Report PISIS-2003-02, Universidad Autónoma de Nuevo León, Facultad de Ingeniería Mecánica y Eléctrica, División de Posgrado en Ingeniería de Sistemas, Mexico., 2003.

2. GRASP and tabu search algorithms for computing the forwarding index in a graph

   E. Arráiz, A. Martínez, O. Meza, and M. Ortega

   In Proceedings of MIC'2001, pages 367-370, July 16-20 2001.

3. Multi-exchange neighborhood search structures for the capacitated minimum spanning tree problem

   R.K. Ahuja, J.B. Orlin, and D. Sharma

   Mathematical Programming, 91:71-97, 2001.

4. A composite very large-scale neighborhood structure for the capacitated minimum spanning tree problem

   R.K. Ahuja, J.B. Orlin, and D. Sharma

   Operations Research Letters, 31(3):185-194, 2003.

5. On maximum clique problems in very large graphs

   J. Abello, P.M. Pardalos, and M.G.C. Resende

   In J. Abello and J. Vitter, editors, External memory algorithms and visualization, volume 50 of DIMACS Series on Discrete Mathematics and Theoretical Computer Science, pages 119-130. American Mathematical Society, 1999.

6. Massive quasi-clique detection

   J. Abello, M.G.C. Resende, and S. Sudarsky

   Lecture Notes in Computer Science, 2286:598-612, 2002.

7. Randomized algorithms for scene recognition by inexact graph matching

   M.C. Boeres, C.C. Ribeiro, and I. Bloch

   Technical report, Computer Science Department, Catholic University of Rio de Janeiro, Rio de Janeiro, Brazil, 2003.

8. Parallel randomized heuristics for the set covering problem

   M.S. Fiorenzo Catalano and F. Malucelli

   Technical report, Transportation and traffic engineering section, Delft U. of Technology, 2600 AG Delft, The Netherlands, 2000. To appear in International J. of Computer Research.

9. A GRASP heuristic for the mixed Chinese postman problem

   A. Corberán, R. Martí, and J.M. Sanchís

   European Journal of Operational Research, 142:70-80, 2002.

10. Local search with perturbation for the prize-collecting Steiner tree problems in graphs

    S.A. Canuto, M.G.C. Resende, and C.C. Ribeiro

    Networks, 38:50-58, 2001.

11. A GRASP heuristic for the capacitated minimum spanning tree problem using a memory-based local search strategy

    M.C. de Souza, C. Duhamel, and C.C. Ribeiro

    In M.G.C. Resende and J.P. de Sousa, editors, Metaheuristics: Computer decision-making, pages 627-658. Kluwer Academic Publishers, 2003.

12. Randomized heuristics for the MAX-CUT problem

    P. Festa, P.M. Pardalos, M.G.C. Resende, and C.C. Ribeiro

    Optimization Methods and Software, 7:1033-1058, 2002.

13. A probabilistic heuristic for a computationally difficult set covering problem

    T.A. Feo and M.G.C. Resende

    Operations Research Letters, 8:67-71, 1989.

14. A greedy randomized adaptive search procedure for maximum independent set

    T.A. Feo, M.G.C. Resende, and S.H. Smith

    Operations Research, 42:860-878, 1994.

15. A GRASP algorithm for the single source uncapacitated minimum concave-cost network flow problem

    K. Holmqvist, A. Migdalas, and P.M. Pardalos

    In P.M. Pardalos and D.-Z. Du, editors, Network design: Connectivity and facilities location, volume 40 of DIMACS Series on Discrete Mathematics and Theoretical Computer Science, pages 131-142. American Mathematical Society, 1998.

16. Maximally disjoint solutions of the set covering problem

    P.L. Hammer and D.J. Rader, Jr.

    Journal of Heuristics, 7:131-144, 2001.

17. Efficient algorithms for location and sizing problems in network design

    K. Kumaran, A. Srinivasan, Q. Wang, S. Lanning, and K.G. Ramakrishnan

    In Global Telecommunications Conference, 2001 (GLOBECOM '01), volume 4, pages 2586-2590. IEEE, 2001.

18. A GRASP for coloring sparse graphs

    M. Laguna and R. Martí

    Computational Optimization and Applications, 19:165-178, 2001.

19. Arc crossing minimization in graphs with GRASP

    R. Martí

    IIE Transactions, 33:913-919, 2001.

20. The edge-weighted clique problem: Valid inequalities, facets and polyhedral computations

    E.M. Macambira and C.C. de Souza

    Technical Report IC-97-14, Instituto de Computac cão, Universidade Estadual de Campinas, Campinas, Brazil, 1997.

21. A GRASP for the maximum clique problem with weighted edges

    E.M. Macambira and C.C. de Souza

    In Proceedings of the XXIX Brazilian Symposium on Operations Research, page 70, October 1997.

22. Incremental bipartite drawing problem

    R. Martí and V. Estruch

    Computers and Operations Research, 28:1287-1298, 2001.

23. Heuristics and meta-heuristics for 2-layer straight line crossing minimization

    R. Martí and M. Laguna

    Discrete Applied Mathematics, 127:665-678, 2003.

24. A GRASP algorithm for the maximum weighted edge subgraph problem

    E.M. Macambira and C.N. Meneses

    Technical report, Department of Statistics and Computation, University of Ceará, Fortaleza, CE 60740-000 Brazil, 1998.

25. Expading neighborhood GRASP for the Traveling Salesman Problem

    Y. Marinakis and A. Migdalas

    Technical report, Technical University of Crete, Chania 73100, Greece, 2003.

26. GRASP metaheuristics to the generalized covering tour problem

    L. Motta, L.S. Ochi, and C. Martinhon

    In Proceedings of MIC'2001, pages 387-391, July 16-20 2001.

27. Greedy randomized adaptive search procedures for the Steiner problem in graphs

    S.L. Martins, P.M. Pardalos, M.G.C. Resende, and C.C. Ribeiro

    In P.M. Pardalos, S. Rajasekaran, and J. Rolim, editors, Randomization methods in algorithmic design, volume 43 of DIMACS Series on Discrete Mathematics and Theoretical Computer Science, pages 133-145. American Mathematical Society, 1999.

28. A parallel GRASP for the Steiner tree problem in graphs using a hybrid local search strategy

    S.L. Martins, M.G.C. Resende, C.C. Ribeiro, and P.M. Pardalos

    Journal of Global Optimization, 17:267-283, 2000.

29. A parallel GRASP for the Steiner problem in graphs

    S.L. Martins, C.C. Ribeiro, and M.C. Souza

    In A. Ferreira and J. Rolim, editors, Proceedings of IRREGULAR'98 -- 5th International Symposium on Solving Irregularly Structured Problems in Parallel, volume 1457 of Lecture Notes in Computer Science, pages 285-297. Springer-Verlag, 1998.

30. A greedy random adaptive search procedure for the maximal planar graph problem

    I.H. Osman, B. Al-Ayoubi, and M. Barake

    Computers and Industrial Engineering, 45:635-651, 2003.

31. A greedy random adaptive search procedure for the weighted maximal planar graph problem

    I.H. Osman, B. Al-Ayoubi, M. Barake, and M. Hasan

    Technical report, School of Business and Center for Advanced Mathematical Sciences, American University of Beirut, Beirut, Lebanon, 2000.

32. Linear programming based meta-heuristics for the weighted maximal planar graph

    I.H. Osman, M. Hasan, and A. Abdullah

    Journal of the Operational Research Society, 53:1142-1149, 2002.

33. A greedy randomized adaptive search procedure for the feedback vertex set problem

    P.M. Pardalos, T. Qian, and M.G.C. Resende

    Journal of Combinatorial Optimization, 2:399-412, 1999.

34. An exact parallel algorithm for the maximum clique problem

    P.M. Pardalos, M.G.C. Resende, and J. Rappe

    In R. De Leone, A. Murli, P.M. Pardalos, and G. Toraldo, editors, High performance algorithms and software in nonlinear optimization, pages 279-300. Kluwer Academic Publishers, 1998.

35. Computing approximate solutions of the maximum covering problem using GRASP

    M.G.C. Resende

    Journal of Heuristics, 4:161-171, 1998.

36. Algorithm 787: Fortran subroutines for approximate solution of maximum independent set problems using GRASP

    M.G.C. Resende, T.A. Feo, and S.H. Smith

    ACM Transactions on Mathematical Software, 24:386-394, 1998.

37. Heurísticas para o problema de síntese de redes a 2-caminhos

    I.C.M. Rosseti

    PhD thesis, Department of Computer Science, Catholic University of Rio de Janeiro, Rio de Janeiro, Brazil, July 2003.

38. A GRASP for graph planarization

    M.G.C. Resende and C.C. Ribeiro

    Networks, 29:173-189, 1997.

39. Algorithm 797: Fortran subroutines for approximate solution of graph planarization problems using GRASP

    C.C. Ribeiro and M.G.C. Resende

    ACM Transactions on Mathematical Software, 25:341-352, 1999.

40. A parallel GRASP for the 2-path network design problem

    C.C. Ribeiro and I. Rosseti

    Lecture Notes in Computer Science, 2004:922-926, 2002.

41. A hybrid GRASP with perturbations for the Steiner problem in graphs

    C.C. Ribeiro, E. Uchoa, and R.F. Werneck

    INFORMS Journal on Computing, 14:228-246, 2002.