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