ACM Transactions on Mathematical Software, vol. 25, pp. 341-352, 1999.
We describe Fortran subroutines for finding approximate solutions of the maximum planar subgraph problem (graph planarization) using a Greedy Randomized Adaptive Search Procedure (GRASP). The design and implementation of the code are described in detail. Computational results with the subroutines illustrate the quality of solutions found as a function of number of GRASP iterations. Source code of the FORTRAN subroutines can be downloaded.
PostScript file of full paper
Mauricio G.C. Resende's Home PageLast modified: 27 June 2002