Printer Friendly

Algorithm 797: Fortran Subroutines for Approximate Solution of Graph Planarization Problems Using GRASP.

1. INTRODUCTION

A graph is said to be planar if it can be drawn on the plane in such a way that no two of its edges cross. Given a graph G = (V, E) with vertex set V and edge set E, the objective of graph planarization is to find a minimum cardinality subset of edges F [subset or equal to] E such that the graph G' = (V, E\F) resulting from the removal of the edges F from G is planar. This problem is also known as the maximum planar subgraph problem. A maximal planar subgraph is a planar subgraph G' = (V', E') of G = (V, E), such that the addition of any edge [element of] C E\E' to G' destroys the planarity of the subgraph.

Graph planarization is known to be NP-hard [Liu and Geldmacher 1977], and most algorithms to date attempt to find good approximate solutions. Several graph planarization heuristics have been proposed in the literature. Jayakumar et al. [1989] describe two O([|V|.sup.2]) planarization algorithms, based on the Lempel, Even, and Cederbaum planarity testing algorithm [Lempel et al. 1966]. Cai et al. [1993] proposed an O(|E|log|V|) algorithm for finding a maximal planar subgraph based on the Hopcroft and Tarjan planarity testing algorithm [Hopcroft and Tarjan 1974]. Another O(|E|log|V|) algorithm was also proposed by Di Battista and Tamassia [1989], based on an O(log|V|) time-per-operation strategy to the problem of maintaining a planar graph under edge additions.

Takefuji and Lee [1989] described a parallel heuristic for planarization based on neural networks. They use an arbitrary sequencing of the vertices, placing them along a line, followed by the use of a neural network for determining two sets of edges that may be represented without crossings above and below that line, respectively. The two-phase approach of Takefuji and Lee was extended and improved by Goldschmidt and Takvorian [1994]. Junger and Mutzel [1996] designed an exact branch-and-cut algorithm for the maximum planar subgraph problem using facet-defining inequalities. A heuristic based on the branch-and-cut algorithm stops with a feasible, though not necessarily optimal, solution.

Resende and Ribeiro [1997] further extended the two-phase approach, applying the framework of the GRASP (Greedy Randomized Adaptive Search Procedure) metaheuristic. The Fortran subroutines described in this article are an implementation of that GRASP.

We next describe the organization of this article. Section 2 describes the GRASP for graph planarization. The Fortran implementation is outlined in Section 3, and its usage is described in Section 4. In Section 5, we present some computational results illustrating the effectiveness of this approximate solution procedure.

2. GRASP FOR GRAPH PLANARIZATION

A GRASP [Feo and Resende 1995] is an iterative process, where each iteration consists of two phases: construction and local search. The construction phase builds a feasible solution, whose neighborhood is explored by local search. The best solution over all iterations is returned as the result. Figure 1 illustrates a generic GRASP implementation in pseudocode. The GRASP takes, as input, parameters for setting the candidate list size, maximum number of iterations, and the seed for the random-number generator. After reading the instance data (line 1), the iterations are carried out in lines 2-6. Each iteration consists of the construction phase (line 3), the local search phase (line 4), and, if necessary, the incumbent solution update (line 5).

Fig. 1. A generic GRASP pseudocode.
procedure GRASP(ListSize, MaxIter, RandomSeed)
1   Input Instance ();
2   do k = 1,..., MaxIter [right arrow]
3        ConstructGreedyRandomizedSolution (ListSize, RandomSeed);
4        LocalSearch(BestSolutionFound);
5        UpdateSolution(BestSolutionFound);
6   od;
7   return BestSolutionFound
endGRASP;


In the graph planarization problem, the construction phase (see Figure 2) of each GRASP iteration consists in devising a sequence [Pi] of the set of vertices V of the input graph G. The vertices of G are placed on a line according to this sequence [Pi]. The procedure takes as input the graph G = (V, E) to be planarized, the restricted candidate list (RCL) parameter a (0 [is less than or equal to] [Alpha] [is less than or equal to] 1), and a seed for the pseudorandom-number generator. Let [deg.sub.G](v) be the degree of vertex v with respect to G, and let d = [min.sub.v [element of] v]{[deg.sub.G](v)} and d = [max.sub.v [element of] v]{[deg.sub.G](v)}. The first vertex in the sequence is determined in lines 1-3, where all vertices having degree in the range [d, [Alpha](d - d) + d] are placed in the RCL and where a single vertex is selected at random from the list. The working vertex set V and graph [G.sub.1] are defined in line 4.

Fig. 2. Pseudocode of GRASP construction phase.
procedure ConstructGreedyRandomizedSolution([Alpha],seed,V,E,[Pi])
1 d = [min.sub.v [element of] v]{[deg.sub.G](v)}; d = [max.sub.v
[element of] v]{[deg.sub.G](v)};
2 RCL :{v [element of] V : d [is less than or equal to] [deg.sub.G]
(v) [is less than or equal to] [Alpha] (d - d) + d};
3 [v.sub.1] = random(seed, RCL);
4 V = V \ {[v.sub.1]}; [G.sub.1] : graph induced on G by V;
5 do k = 2,...,|V| [right arrow]
6      d = [min.sub.v [element of] v]{[deg.sub.Gk-1] (v)};
d = [max.sub.v [element of] v]{[deg.sub.Gk-1] (v)};
7      [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]
8            [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]
9      fi;
10     [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]
11            [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]
12     fi;
13     [v.sub.k] = random(seed, RCL);
14     V = V \ {[v.sub.k]}; [G.sub.k] = graph induced on G by V;
15 od
16 return [Pi] = ([v.sub.1],[v.sub.2],...,[v.sub.|v|])
end ConstructGreedyRandomizedSolution;


The loop from line 5 to 15 determines the sequence of the remaining |V| -- 1 vertices. To assign the kth vertex (iteration k of the loop) two cases can occur. Define [G.sub.k] to be the graph induced on G by V\{[v.sub.1], [v.sub.2], ... , [v.sub.k]}. Let [ADJ.sub.Gk-1]([v.sub.k-1]) be the set of vertices of [G.sub.k-1] adjacent to [V.sub.k-1] in G. The RCL is made up of all vertices in [ADJ.sub.Gk-1] ([V.sub.k-1]) having degree in the range [d, [Alpha](d - d) + d] in [G.sub.k]. Otherwise, if [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII], the RCL is made up of all unselected vertices having degree in the range [d, [Alpha](d - d) + d] in [G.sub.k]. In line 13, the kth vertex in the sequence is determined by selecting a vertex, at random, from the RCL. The greedy function is adapted in line 14 where the working vertex set and graph are updated. The vertex sequence [Pi] = ([v.sub.1], [v.sub.2], ... , [v.sub.|v|]) is returned, where [Pi](v) denotes the relative position of vertex v c V within vertex sequence II. Furthermore, let [e.sub.1] = (a, b) and [e.sub.2] = (c, d) be two edges of G, such that, without loss of generality, [Pi](a) [is less than] [Pi](b) and [Pi](c) [is less than] [Pi](d). These edges are said to cross with respect to sequence [Pi] if [Pi](a) [is less than] [Pi](c) [is less than] [Pi](b) [is less than] [Pi](d) or [Pi](c) [is less than] [Pi](a) [is less than] [Pi](d) [is less than] [Pi](b).

The vertex ordering obtained at the end of the construction phase may be improved by attempting to reduce the number of crossing edges by locally searching a neighborhood of the current vertex sequence prior to the second phase. We next describe such a local search procedure. To do so, let us define the neighborhood N([Pi]) of the vertex sequence [Pi] to be formed by all vertex sequences [Pi]' differing in exactly two positions, i.e.,

N([Pi]) = {[Pi]' = ([v'.sub.1], [v'.sub.2], ... , [v'.sub.|v|]): [v'.sub.i] = [v.sub.i], [inverted A]i [is not equal to] j, k, [v'.sub.j] = [v.sub.k], [v'.sub.k] = [v.sub.j]}.

Let [X.sub.([Pi])] be the number of edge-pairs that cross with respect to vertex sequence [Pi]. The pseudocode in Figure 3 describes the local search procedure used in the GRASP. In our implementation, we use a slightly more restricted neighborhood, in which only consecutive vertices can be exchanged.

Fig. 3. Pseudocode of GRASP local search phase.
procedure LocalSearch(V,E,[Pi])
1   do [Pi] is not locally optimal [right arrow]
2           Find [Pi]' [element of] N([Pi]) such that X([Pi]')
[is less than] X([Pi]);
3           H = H';
4   od
5   return [Pi] = ([v.sub.1],[v.sub.2],...,[v.sub.|v|])
end LocalSearch;


Let H = (E, I) be a graph where each of its vertices corresponds to an edge of the input graph G. Vertices [e.sub.1] and [e.sub.2] of H are connected by an edge if the corresponding edges of G cross with respect to sequence [Pi]. A graph is called an overlap graph if its vertices can be placed in one-to-one correspondence with a family of intervals on a line. Two intervals are said to overlap if they cross and none is contained in the other. Two vertices of the overlap graph are connected by an edge if and only if their corresponding intervals overlap. Hence, the graph H as constructed above is the overlap graph associated with the representation of G defined by sequence [Pi].

Following Goldschmidt and Takvorian [1994], the next phase of our procedure consists in two-coloring a maximum number of the vertices of the overlap graph H such that each of the two color classes B (blue) and R (red) forms an independent set. Equivalently, the second phase seeks a maximum induced bipartite subgraph of the overlap graph H, i.e., a bipartite subgraph having the largest number of vertices. This problem is equivalent to drawing the edges of the input graph G above or below the line where its vertices have been placed, according to sequence II. Since the decision version of the problem of finding a maximum induced bipartite subgraph of an overlap graph is NP-complete [Sarrafzadeh and Lee 1989], a greedy algorithm is used in GT to construct a maximal induced bipartite subgraph of the overlap graph. This algorithm finds a maximum independent set B [subset or equal to] E of the overlap graph H = (E, I), reduces the overlap graph by removing from it the vertices in B and all edges incident to vertices in B, and then finds a maximum independent set R [subset or equal to] E \ B in the remaining overlap graph H' = (E \ B, I'). The two independent sets obtained induce a bipartite subgraph of the original overlap graph, not necessarily with a maximum number of vertices. This procedure has polynomial time complexity, since finding the maximum independent set of an overlap graph has been shown by Gavril [1973] to be polynomially solvable in time O(|[E.sup.3]|), where |E| is the number of vertices of the overlap graph H = (E, I) (see also Golumbic [1980] for another description of this algorithm). Pseudocode for the two-coloring procedure is given in Figure 4.

Fig. 4. Pseudocode of the two-coloring procedure.
procedure TwoColoring(V,E,[Pi],B,R)
1   BuildOverlapGraph(V, E, [Pi], I);
2   FindMaxIndependentSet (E, I, B);
3   ReduceOverlapGraph(E, I, B, I');
4   FindMaxIndependentSet (E \ B, I', R);
5   return B, R
end TwoColoring;


The two-coloring heuristic outputs three edge sets: B (blue edges), R v(red edges), and P (the remaining edges, which we refer to as the pale edges). By construction, B, R, and P are such that no red or pale edge can be colored blue. Likewise, pale edges cannot be colored red. However, if there exists a pale edge p [element of] P such that all blue edges that cross with p (let [B.sub.p] [subset or equal to] B be the set of those blue edges) do not cross with any red edge r [element of] R, then all blue edges b [element of] [B.sub.p] can be colored red and p can be colored blue. This reassignment of color classes increases the size of the planar subgraph by one edge. Figure 5 shows pseudocode for procedure Enlarge-Planar that seeks pale and blue edges allowing the above color class reassignment and enlarges the planar subgraph when such edges are encountered. The pale edges are scanned in do loop 1-12, while loop 3-10 scans the blue edges to construct the set [B.sub.p], whose elements are saved in line 5. If a blue edge b E [element of] [B.sub.p] crosses any red edge, the set [B.sub.p] is discarded (line 7), and a new pale edge is scanned. If no edge b [element of] [B.sub.p] crosses red edges, then all blue edges b [element of] [B.sub.p] are colored red, and the pale edge p is colored blue in line 11. This procedure has time complexity O(|[E.sup.3]|).

Fig. 5. Pseudocode of local search procedure to enlarge planar subgraph.
procedure EnlargePlanar(B, R, P, V)
1   do p [element of] P [right arrow]
2        [B.sub.p] = 0;
3        do b [element of] B [right arrow]
4             if p and b cross [right arrow]
5                    [B.sub.p] = [B.sub.p] [union] {b};
6                    do r [element of] R [right arrow]
7                         if r and b cross [right arrow] goto 12
fi;
8                    od;
9             fi;
10       od;
11       (B, R, P) = (B [union] {p} \ [B.sub.p], R [union]
            [B.sub.p], P \ {p});
12  od;
13  return B, R
 end EnlargePlanar;


By incorporating the two-coloring heuristic and the graph-enlarging procedure to the construction and local search phases, we have a GRASP for graph planarization, whose pseudocode is given in Figure 6.

Fig. 6. Pseudocode of GRASP for graph planarization.
procedure GRASPforGP ([Alpha],seed,MaxIter,V ,E,II*,R*)
1   do k = 1, 2, ...,MaxIter [right arrow]
2        ConstructGreedyRandomizedSolution([Alpha],seed,V ,E,II);
3        LocalSearch(V,E,II);
4        TwoColoring(V,E,II,B,R);
5        P = E\ (B [union] R);
6        EnlargePlanar(B,R,P,V);
7        UpdateSolution(II,B,R,II*,B*,R*);
8   od
9   return II*, B*, R*
end GRASPforGP;


The procedure is repeated MaxIter times. In each iteration, a greedy randomized solution (vertex sequence H) is constructed in line 2. In line 3, the local search attempts to produce a vertex sequence that has fewer edge-pair crossings than the one generated in line 2. The vertex sequence H is given as input to the two-coloring heuristic in line 4 to produce a planar subgraph of G. In lines 5 and 6 the procedure to enlarge the current planar subgraph is applied. If the cardinality of the edge-set of the subgraph found in line 6 is the largest found so far, it is recorded in line 7.

3. DESIGN AND IMPLEMENTATION OF THE SUBROUTINES

The code is implemented in ANSI standard Fortran 77, and runs without any modifications on UNIX environments. It has also run on other environments with little or no change. Input, output, variable, and array declarations and parameter settings are all performed in a separate driver module. Therefore, usage and experimentation with the code are relatively simple.

The optimization package consists of three files: Makefile, driver, f, and gmpsg.f. Also included in the distribution is a sample input data file, sample.dat.

4. USAGE OF THE SUBROUTINES

The subroutines in file gmpsg.f carry out the approximate optimization of the maximum planar subgraph problem. The user interface with them is subroutine gmpsg, which must be called from a driver program. In addition to a number of auxiliary arrays, the driver passes (1) the following representation of the input graph

n: Number of nodes in graph

m: Number of arcs in graph

arc1: Integer array where arc1 (i) is node 1 of arc i

arc2: Integer array where arc2 (i) is node 2 of arc i

and (2) the following array dimensions:

nmax: Dimension of number of nodes declared in driver . f,

mmax: Dimension of number of arcs declared in driver . f.

The sample driver program for gmpsg included in the distribution (driver. f) is set for problems of dimension n [is less than or equal to] 200 vertices and m [is less than or equal to] 1600 edges. The input/output parameters that define Fortran input/output devices are set to the standard values in = 5 and iout = 6. These parameters can be set by the user for problems of different dimension or if an alternate input or output device is required.

All variables and arrays needed by subroutine gmpsg are defined in the main program in driver, f. Subroutines readp and outsol, also provided in driver . f, are examples of code that can be used for input and output, respectively. The driver program calls readp, which reads the input data and returns an error condition errcnd = 0 if no error in the input data is detected or errcnd = 1 if the declared number of nodes n [is greater than] nmax, errcnd = 2 if the declared number of arcs m [is greater than] mmax, or errcnd = 9 if the number of arcs provided in the input is less than the declared number of arcs m. If errcnd [is greater than] 0, then driver, f calls subroutine errmsg (provided in file gmpsg, f) which prints the error message, and execution is halted.

Five parameters that control the execution of the algorithm need to be set before the optimization module is called: alpha, the RCL parameter, is a real number that must satisfy 0 [is less than or equal to] alpha [is less than or equal to] 1; look4, a stopping parameter that forces GRASP to stop if a planar subgraph of size at least look4 is found, is an integer that must satisfy 0 [is less than or equal to] look4 [is less than or equal to] m; maxitr, the maximum number of GRASP iterations, is an integer such that maxitr [is greater than] 0; prttyp, the output option parameter, is an integer that is set to 0 (silent run; gmpsg does not write anything), 1 (gmpsg prints out solution improvements), or 2 (gmpsg prints out the solution found in each GRASP iteration); and seed, the pseudorandom-number generator seed, an integer such that 1 [is less than or equal to] seed [is less than or equal to] [2.sup.31] -- 1. The default settings for alpha, look4, maxitr, prttyp, and seed are, respectively, 0.1, m, 2048, 1, and 270001.

If errcnd = 0 is returned by readp, then driver, f calls the optimization subroutine gmpsg, which attempts to find a large planar subgraph of the input graph. Subroutine 9mpsg returns error condition errcnd indicating the status of the optimization. Error condition errcnd can have the following values:

errcnd = 1 if a n [is greater than] nmax;

errcnd = 2 if a m [is greater than] mmax;

errcnd = 3 if an input node is less than I or greater than m;

errcnd = 4 if alpha [is less than] 0 or alpha [is greater than] 1;

errcnd = 5 if look4 [is less than] 1 or look4 [is greater than] m;

errcnd = 6 if maxitr [is less than] 1;

errcnd = 7 if prttyp # 0,1,2;

errcnd = 8 if seed [is less than] 1 or seed [is greater than] 2147483647.

As an example, consider the instance g1 of dimension 10 vertices by 22 arcs (of Goldschmidt and Takvorian [1994]) with input file shown in Figure 7. Running the driver program using the default settings on instance g1 produces the output shown in Figure 8. The output lists each iteration for which an improving solution was found and describes the best solution found by listing the vertex permutation, and the blue and red arcs.

Fig. 7. Input file of graph planarization instance g1.
10 22

1  10   1   9   1  7   1   5    1   2   2   8    2  7   2  4
2   3   3  10   3  6   3   5    4   8   4   5    5  6   6  8
6   7   7   9   7  8   8  10    8   9   9  10


Fig. 8. Sample output of driver for graph planarization instance g1.
itr:               1 size:            20 improvement

Execution terminated with no error.

GRASP solution --

largest planar subgraph found in iteration:   1

size of largest     planar   subgraph:       20
avg size of         planar   subgraph:       19.2
blue arcs in        planar   subgraph:       16
red arcs in         planar   subgraph:        4

vrtx permut:             4           5                 6      7
vrtx permut:             2           1                 9      8

blue arcs:               1           2           3      5     7
blue arcs:              11          12          13     14    15
blue arcs:              16          17          18     19    21
blue arcs:              22

red arcs:                6           8           9     20


5. COMPUTATIONAL RESULTS

In this section, we illustrate the effectiveness of the subroutines by running the planarization procedure on a subset of the test problems used by Resende and Ribeiro [1997]. The experiment was limited to all of those test problems having at least 50 and at most 200 nodes with at most 750 arcs (a total of 51 instances). Each run of GRASP was done using the default parameter settings as defined in file driver, f of the distribution, i.e., alpha = 0.1, look4 = m, maxitr = 2048, prttyp = 1, and seed = 270001.

For each problem considered in the experiment, Tables I and II show the size (number of arcs) of the incumbent solution as a function of GRASP iterations. The incumbent solutions at iterations 2, 8, 32, 128, 512, and 2048 are listed. Figure 9 shows all incumbents at iterations 1, 2, 4, 8, 16, 32, 64, 128, 256, 512, 1024, and 2048, as well as the average values of the incumbent solutions at those iterations (dotted line).

[Figure 9 ILLUSTRATION OMITTED]

Table I. Number of Arcs in Incumbent Solution as a Function of GRASP Iteration: Part 1
                          GRASP Iteration

Name            2      8     32     128    512    2048

g2.cimi        160    160    165    165    165     165
g13            129    130    131    133    134     135
g14            141    141    143    143    143     143
g15            142    143    144    144    144     144
g16            184    187    190    190    191     193
g17            218    225    231    231    231     234

rg50.1         83     87     87     87     90      90
rg50.2         91     91     92     92     94      95
rg50.3         98     98     100    100    101     103
rg50.4         98     98     100    100    100     101
rg50.5         98     101    102    102    105     105

rg75.1         122    126    126    126    126     126
rg75.2         126    127    128    129    130     131
rg75.3         129    129    130    130    131     132
rg75.4         132    134    137    137    138     140
rg75.5         131    136    139    139    141     143

rg100.1        150    153    156    159    159     161
rg100.2        158    159    163    163    163     164
rg100.3        153    161    162    162    163     164
rg100.4        164    169    170    172    173     173
rg100.5        172    178    182    187    187     187

rg150.1        217    217    222    222    225     226
rg150.2        218    219    219    221    223     224
rg150.3        226    230    231    234    234     237
rg150.4        226    228    232    235    235     236
rg150.5        232    234    239    239    239     240

rg200.1        276    276    278    281    281     284
rg200.2        277    277    279    283    283     285
rg200.3        293    296    303    303    303     304
rg200.4        302    302    308    308    309     310
rg200.5        300    303    307    307    311     311


Table II. Number of Arcs in Incumbent Solution as a Function of GRASP Iteration: Part 2
                            GRASP Iteration

Name           2      8     32     128    512   2048

tg100.1       239    247    257    257    258    258
tg100.2       227    247    252    253    265    265
tg100.3       237    248    252    252    256    262
tg100.4       235    244    249    254    254    262
tg100.5       241    244    244    250    252    254
tg100.6       231    231    237    242    244    253
tg100.7       219    229    240    244    244    246
tg100.8       227    232    236    247    247    248
tg100.9       230    235    235    237    239    241
tg100.10      219    229    230    235    236    244

tg200.1       463    463    477    477    491    491
tg200.2       435    460    471    478    480    488
tg200.3       463    478    485    495    502    504
tg200.4       462    469    469    476    488    493
tg200.5       448    458    463    473    474    486
tg200.6       462    462    462    468    477    482
tg200.7       426    431    446    450    452    466
tg200.8       443    449    458    461    492    492
tg200.9       434    451    451    453    461    465
tg200.10      443    443    443    461    468    468


REFERENCES

CAI, J., HAN, X., AND TARJAN, R. E. 1993. An O(m log n)-time algorithm for the maximal planar subgraph problem. SIAM J. Comput. 22, 6 (Dec. 1993), 1142-1162.

DI BATTISTA, G. AND TAMASSIA, R. 1989. Incremental planarity testing. In Proceedings of the 30th IEEE Symposium on Foundations of Computer Science (FOCS '89, Research Triangle Park, NC, Oct. 30-Nov. 1) IEEE Computer Society Press, Los Alamitos, CA, 436-441.

FEO, T. AND RESENDE, M. 1995. Greedy randomized adaptive search procedures. J. Global Optim. 6, 109-133.

GAVRIL, F. 1973. Algorithms for a maximum clique and a maximum independent set of a circle graph. Networks 3, 261-273.

GOLDSCHMIDT, O. AND TAKVORIAN, A. 1994. An efficient graph planarization two-phase heuristic. Networks 24, 69-73.

GOLUMBIC, M. 1980. Algorithmic Graph Theory and Perfect Graphs. Academic Press, Inc., New York, NY.

HOPCROFT, J. AND TARJAN, R. 1974. Efficient planarity testing. J. ACM 21, 4 (Oct.), 549-568.

JAYAKUMAR, R., THULASIRAMAN, K., AND SWAMI, N. 1989. O([n.sup.2]) algorithms for graph planarization. IEEE Trans. Comput.-Aided Des. 8, 257-267.

JUNGER, M. AND MUTZEL, P. 1996. Maximum planar subgraphs and nice embeddings: Practical layout tools. Algorithmica 16, 33-59.

LEMPEL, A., EVEN, S., AND CEDARBAUM, I. 1966. An algorithm for planarity testing of graphs. In Proceedings of the International Symposium on Theory of Graphs (Rome) Gordon and Breach Science Publishers, Inc., Langhorn, PA, 215-232.

LIU, P. AND GELDMACHER, R. 1977. On the deletion of nonplanar edges of a graph. In Proceedings of the 10th Southeastern Conference on Combinatorics, Graph Theory, and Computing (Boca Raton, FL) 727-738.

RESENDE, M. G. C. AND RIBEIRO, C. C. 1997. A GRASP for graph planarization. Networks 29, 173-189.

SARRAFZADEH, M. AND LEE, D. 1989. A new approach to topological via minimization. IEEE Trans. Comput.-Aided Des. 8, 890-900.

TAKEFUJI, Y. AND LEE, K. 1989. A near-optimum parallel planarization algorithm. Science 245, 1221-1223.

Received: September 1997; revised: March 1999; accepted: May 1999

CELSO C. RIBEIRO Catholic University of Rio de Janeiro and MAURICIO G. C. RESENDE AT&T Labs Research

Authors' addresses: C. C. Ribeiro, Department of Computer Science, Catholic University of Rio de Janeiro, Rio de Janeiro, RJ 22453-900, Brazil; email: celso@inf.puc-rio.br; M. G. C. Resende, Information Sciences Research Center, AT&T Labs Research, Room C241, 180 Park Avenue, Florham Park, NJ 07932; email: mgcr@Wresearch.att.com. Permission to make digital/hard copy of part or all of this work for personal or classroom use is granted without fee provided that the copies are not made or distributed for profit or commercial advantage, the copyright notice, the title of the publication, and its date appear, and notice is given that copying is by permission of the ACM, Inc. To copy otherwise, to republish, to post on servers, or to redistribute to lists, requires prior specific permission and/or a fee.
COPYRIGHT 1999 Association for Computing Machinery, Inc.
No portion of this article can be reproduced without the express written permission from the copyright holder.
Copyright 1999 Gale, Cengage Learning. All rights reserved.

Article Details
Printer friendly Cite/link Email Feedback
Author:RIBEIRO, CELSO C.; RESENDE, MAURICIO G. C.
Publication:ACM Transactions on Mathematical Software
Article Type:Statistical Data Included
Geographic Code:3BRAZ
Date:Sep 1, 1999
Words:4594
Previous Article:The RISC BLAS: A Blocked Implementation of Level 3 BLAS for RISC Processors.
Next Article:Algorithm 798: High-Dimensional Interpolation Using the Modified Shepard Method.
Topics:

Terms of use | Privacy policy | Copyright © 2021 Farlex, Inc. | Feedback | For webmasters |