A GRASP for Graph Planarization

Mauricio G.C. Resende and Celso C. Ribeiro

Networks, vol.29, pp. 173-189, 1997.

ABSTRACT

A greedy randomized adaptive search procedure (GRASP) is a metaheuristic for combinatorial optimization.  In this paper, we describe a GRASP for the graph planarization problem, extending the heuristic of Goldschmidt and Takvorian [Networks 24, pp.  69-73, 1994].  We review basic concepts of GRASP:  construction and local search algorithms.  The implementation of GRASP for graph planarization is described in detail.  Computational experience on a large set of standard test problems is presented.  On almost all test problems considered, the new heuristic either matches or finds a better solution than previously described graph planarization heuristics.  In several cases, previously unknown optimal solutions are found.

PostScript file of full paper

Go back

Mauricio G.C. Resende's Home Page

Last modified: 27 June 2002

Copyright Notice