@incollection{BibDidLioNon02a, author = "C. Binucci and W. Didimo and G. Liotta and M. Nonato", title = "Labeling heuristics for orthogonal drawings", booktitle = "Proceedings of {GD}'98 -- {S}ymposium on {G}raph {D}rawing", series = "Lecture Notes in Computer Science", publisher = "Springer-Verlag", volume = "2265", pages = "139--153", year = "2002", annote = "The authors implement and compare several heuristics including a {GRASP} for computing an orthogonal drawing of a graph with labels among the edges that are not allowed to overlap each other or with edges to which they are not assigned.", } @Article{FerMar99a, author = "E. Fern\'andez and R. Mart\'{\i}", title = "{GRASP} for seam drawing in mosaicking of aerial photographic maps", journal = "Journal of Heuristics", volume = "5", pages = "181--197", year = "1999", annote = "Commercial aerial photographic maps are often so large that it is necessary to produce one map from two or even more photographs. These are combined, two at a time, in a process called {\em mosaicking}. The objective is to make the final map appear to be the product of a single photograph. The most difficult step in the mosaicking process is {\em seam-drawing}. This paper proposes a {GRASP} for solving the seam-drawing process.", } @Article{LagMar99a, author = "M. Laguna and R. Mart\'{\i}", title = "{GRASP} and path relinking for $2$-layer straight line crossing minimization", journal = "{INFORMS} Journal on Computing", volume = "11", pages = "44--52", year = "1999", annote = "This paper develops a {GRASP} for the problem of minimizing straight line crossings in a $2$-layer graph. The method proposed can be coupled with a path relinking strategy to search for improved outcomes. The greedy criterion of the construction phase is based on the degree of the vertices and a value based restricted candidate list is used. Each step of the improvement phase consists in selecting each vertex to be considered for a move. A probabilistic selection rule is used such that vertices with high degree are more likely to be selected first at each step of this process. This paper incorporates to {GRASP} a path relinking strategy to search for improved outcomes. Path relinking generates new solutions by exploring trajectories connecting high quality solutions. Starting from an {\em initiating solution}, path relinking generates a path in the neighborhood space that leads toward the other solutions, called {\em guiding solutions}. This is accomplished by selecting moves that introduce attributes contained in the guiding solutions.", } @Article{MarEst01a, author = "R. Mart\'{\i} and V. Estruch", title = "Incremental bipartite drawing problem", journal = "Computers and Operations Research", volume = "28", pages = "1287--1298", year = "2001", annote = "The goal of limiting the number of arc crossings is a well accepted criterion of how well a graph is drawn. Incremental graph drawing supports interactive updates by users. A {GRASP} is proposed for the incremental arc crossing minimization problem for bipartite graphs. Computational experiments are done on 450 instances and results are compared with a branch and bound algorithm.", } @article{MarLag03a, author = "R. Mart\'{\i} and M. Laguna", title = "Heuristics and meta-heuristics for $2$-layer straight line crossing minimization", journal = {Discrete Applied Mathematics}, volume = {127}, pages = {665-678}, year = "2003", annote = "Extensive computational results are presented using 12 heuristics and two meta-heuristics for the $2$-layer straight line crossing minimization problem. On dense graphs, a tabu search meta-heuristic does best with {GRASP} a close second. On low-density graphs, {GRASP} outperforms all other approaches." } @inproceedings{NgTri03a, author = {K. Ng and B. Trifonov}, title = {Automatic Bounding Volume Hierarchy Generation Using Stochastic Search Methods}, booktitle = {CPSC532D Mini-Workshop "Stochastic Search Algorithms"}, institution = {Department of Computer Science, University of British Columbia, Vancouver, Canada}, month = {April}, annote = {A bounding volume hierarchy is used for improving the efficiency of ray tracing based rendering. To find good hierarchies is a difficult problem, since the number of hierarchies grows exponentially with the number of scene objects. In this paper, a {GRASP} is designed for improving previously proposed heuristics. The greedy function used is based on subdivision points, while local search is basically a perturbation procedure.}, year = {2003} } @article{OsmAyoBar03a, author = {I.H. Osman and B. Al-Ayoubi and M. Barake}, title = {A greedy random adaptive search procedure for the maximal planar graph problem}, journal = {Computers and Industrial Engineering}, volume = {45}, pages = {635--651}, annote ={A {GRASP} is proposed and tested for the weighted maximal planar graph problem. The construction is a randomized version of the Green and Al-Hakim algorithm (1985). A new data structure is introduced, reducing the complexity of the construction from $O(n^3)$ to $O(n^2)$. Local search uses four types of moves proposed by Pesch, Glover, Bartsch, Salewski, and Osman (1995).}, year = {2003} } @techreport{OsmAyoBarHas00a, author = "I.H. Osman and B. Al-Ayoubi and M. Barake and M. Hasan", title = "A greedy random adaptive search procedure for the weighted maximal planar graph problem", institution = "School of Business and Center for Advanced Mathematical Sciences, American University of Beirut", address = "Beirut, Lebanon", year = "2000", annote = "A {GRASP} is proposed and tested for the weighted maximal planar graph problem. The construction is a randomized version of the Green \& Al-Hakim algorithm (1985). A new data structure is introduced, reducing the complexity of the construction from $O(n^3)$ to $O(n^2)$. Local search uses four types of moves proposed by Pesch, Glover, Bartsch, Salewski, and Osman (1995)." } @Article{OsmHasAbd02a, author = "I.H. Osman and M. Hasan and A. Abdullah", title = "Linear programming based meta-heuristics for the weighted maximal planar graph", journal = "Journal of the Operational Research Society", volume = "53", pages = "1142--1149", year = "2002", annote = "To solve the weighted maximal planar graph problem, two meta-heuristics are described, both derived from an ILP relaxation. The first one takes into account only variables with fractional value greater than half in the ILP relaxation to build an initial subgraph from which a planar subgraph is extracted with the help of a {GRASP} and triangulation of faces. The second approach considers only edges having integer value in the ILP relaxation, while the remaining edges are sorted in descending order of their weights. Those edges that do not violate a planarity test are thus candidate for insertion to obtain a feasible solution using {GRASP}.", } @Article{ResRib97a, author = "M.G.C. Resende and C.C. Ribeiro", title = "A {GRASP} for graph planarization", journal = "Networks", year = "1997", volume = "29", pages = "173--189", annote = "A {GRASP} for the graph planarization problem is described, extending the two-phase heuristic of Goldschmidt and Takvorian ({\em Networks}, v. 24, pp. 69--73, 1994). The implementation of the {GRASP} is described in detail. Computational experience on a large set of standard test problems is presented. On almost all test problems considered, the heuristic either matches or finds a better solution than previously described graph planarization heuristics. In several cases, previously unknown optimal solutions are found." } @Article{RibRes99a, author = "C.C. Ribeiro and M.G.C. Resende", title = "Algorithm 797: {Fortran} subroutines for approximate solution of graph planarization problems using {GRASP}", journal = "ACM Transactions on Mathematical Software", volume = "25", pages = "341--352", year = "1999", annote = "This paper describes a set of Fortran subroutines that implements the {GRASP} for graph planarization of Resende and Ribeiro (1997).", }