2005 ACM Symposium on Applied Computing

Heuristic Methods for Graph Coloring Problems

A. Lim, Y. Zhu Q. Lou B. Rodrigues

Department of IEEM Department of CS School of Business
Hong Kong Univ of Sci & Tech National Univ of Singapore Singapore Management Univ
Clear Water Bay 3 Science Drive 2 469 Bukit Timah Road
Kowloon, Hong Kong Singapore Singapore
{iealim,zhuyi}@ust.hk louqin@comp.nus.edu.sg br@smu.edu.sg

ABSTRACT Most of the early work done on this problem can be found
In this work, the Graph Coloring Problem and its general- in: “Cliques, Coloring and Satisfiability, Second DIMACS
izations - the Bandwidth Coloring Problem, the Multicol- Implementation Challenge” [8].
oring Problem and the Bandwidth Multicoloring Problem The Multi-Coloring Problem (with weighted nodes), the
- are studied. A Squeaky Wheel Optimization with Tabu Bandwidth Coloring Problem (with weighted edges) and the
Search heuristic is developed and experiments using bench- Bandwidth Multi-Coloring Problem (with weighted edges
mark geometric test cases show that the algorithm performs and nodes) are generalizations of the GCP and have a range
well for these problems and achieves results for the Band- of applications. The Multi-Coloring Problem can be used,
width Multicoloring Problem which improve on results ob- for example, to schedule jobs with different time require-
tained by other researchers. ments where the set of colors assigned to a node corresponds
to resources (e.g. men) assigned to a job. Here, each node
has a demand of a set of colors which we have to assign to it
Categories and Subject Descriptors ensuring that its neighbors receive disjoint sets (e.g. sets of
F.2.2 [Nonnumerical Algorithms and Problems]: [Se- men). A related application is in scheduling processor tasks
quencing and scheduling] where certain resources cannot be shared concurrently by
certain sets of jobs. The problem of channel frequency as-
Keywords signment arises with different transmitters operating in the
same region which can interfere with each other. This is
Heuristics, Optimization, Tabu Search, Graph Coloring common to mobile or general radio networks. The problem
can be viewed as a multicoloring problem where each node
1. INTRODUCTION of an interference graph has an associated integer weight
The Graph Coloring Problem (GCP) is a well-known NP- representing the number of calls that must be served by
complete problem that has been studied extensively. Heuris- the corresponding base station. We then seek to assign the
tics have been widely used for the GCP (see, for example, weighted number of colors to each node such that adjacent
[1]); these include: iterative Greedy by Culberson and Luo nodes are assigned disjoint sets of colors. The objective is
[3], Tabu Search by Hertz and de Werra [6] and Glover et then to minimize the number of colors used for such an as-
al. [5], DSATUR by Brelaz [1], XRLF by Johnson et al signment. Because of signal interference in networks, adja-
[7]. Other techniques, such as combining of the S-IMPASSE cent transmitters need to operate at different and separated
algorithm with exhaustive search [10] and a distributed col- frequencies. This separation requirement is addressed by
oration neighborhood search [13] have also been introduced. constraining frequencies to be separated by stipulated ”dis-
Among these, the well-known Greedy method is the sim- tances”, usually some positive integer. In such problems,
plest which takes an ordering of nodes of a graph and colors a ”bandwidth” is associated with each frequency.The Band-
these with the smallest color satisfying the constraints that width Coloring and Multi-Coloring Problems have been used
no adjacent nodes are assigned same colors. However, the for channel frequency assignment with interference prob-
Greedy method performs poorly in practice. DSATUR uses lems. In the Fixed Channel Assignment Problem [14], for
a heuristic which changes the ordering of nodes and then example, frequency demand is forecasted and used to de-
uses the Greedy method to color these nodes. Further to termine network requirements and frequencies are assigned
this, exact algorithms, such as branch and bound, have been in advance. In this problem, each cell requires a single as-
used to solve instances with a small number of colors [16]. signed frequency and the Bandwidth Coloring Problem can
be used. In general, when cells require a number of sepa-
rated frequencies, the Bandwidth Multi-Coloring Problem is
used. For example, this problem can be applied to the Fixed
Permission to make digital or hard copies of all or part of this work for Channel Assignment Problem when co-channel constraints,
personal or classroom use is granted without fee provided that copies are adjacent channel constraints and the co-site constraints are
not made or distributed for profit or commercial advantage and that copies included [14].
bear this notice and the full citation on the first page. To copy otherwise, to Recently, Prestwich proposed a combination of local search
republish, to post on servers or to redistribute to lists, requires prior specific
permission and/or a fee.
and constraint propagation in a method called FCNS to
SAC’05, March 13-17, 2005, Santa Fe, New Mexico, USA. solve generalized graph coloring problems [15]. This ap-
Copyright 2005 ACM 1-58113-964-0/05/0003...$5.00.

933
proach is a hybrid of the DSATUR backtracker and the 1 2 3 4

S-IMPASSE local search algorithm and was applied in ex-

K=4
periments to geometric graphs. More recently, Lim et al.
proposed a hybrid method which combines Squeaky Wheel K=3
1 2 3
Optimization (SWO) and hill-climbing techniques which was
also tested on geometric graphs [12]. Squeaky Wheel Opti-
5 6
mization (SWO) is a meta-heuristic in which the core is a K=2
Construct-Analyze-Prioritize cycle [2, 9], which we will in-
K=4
troduce in details in Section 3.3. In this work, we propose
new algorithms which use Tabu Search and SWO. In partic- 5 6 7 8
ular, the SWO with Tabu Search hybrid allows SWO diversi-
fication to be complemented by Tabu Search intensification
in search. We found that this approach gives superior results Figure 1: An instance of the Multi-coloring Problem
when compared with those obtained by Prestwich and Lim
et al. [15, 12] in the Bandwidth Multi-Coloring Problem
1 2 3 4
which is the most difficult of those compared. d=1
This paper is organized as follows. In Section 2, we will K=4

give definitions of the GCP and its generalizations - the

2
K=3

d=1
=
Bandwidth Coloring Problem, the Multi-Coloring Problem

d
1 3 13
d=3
(MCP) and the Bandwidth MCP. In Section 3, we will de- d=3
d=2
scribe the algorithm, its framework and each of its compo-

2
6 9

d=
nents - a Greedy Algorithm, SWO and Tabu Search. In K=2

Section 4, we will present experimental results with com- d=2

K=4
parisons and analysis. In the last section, we will provide a
5 7 9 11
conclusion.

2. PROBLEM DESCRIPTIONS Figure 2: An instance of the Bandwidth Multi-

We give brief descriptions of the problems we study here. coloring Problem
2.1 The Graph Coloring Problem
Problem: Given a graph G(V, E), find a minimum k, 2.4 The Bandwidth Multi-Coloring Problem
and a mapping r : V → {1, ..., k} such that r(i) = r(j) for Problem: Given a graph G(V, E) with node weights k(i)
each edge (i, j) ∈ E. for i ∈ V , and edge weights d(i, j) for (i, j) ∈ E, find a
This is the classical problem when each node in the graph minimum k and subsets S(i) ⊂{1, ..., k} for each i ∈ V , such
is assigned one color and colors for adjacent nodes must be that |S(i)| = k(i) for each i ∈ V and such that S(i) ∩ S(j) =
different. Many practical applications can be modelled as ∅ and where, for each p ∈ S(i) and q ∈ S(j), |p − q| ≥ d(i, j)
GCPs, as we mentioned above. This problem has been well- for each (i, j) ∈ E.
studied. In this problem, each node can only be assigned one This model combines the above two models, and is more
color and there are no “distance” restrictions for adjacent complex. Note that the graph can contain self-loops. For
nodes. The GCP can be extended as in the following. example, d(1, 1) = 2, k(1) = 3 means the 3 colors assigned
to node 1 must have a difference of value 2 at least between
2.2 The Bandwidth Coloring Problem any two of them. The example given in Figure 1 is not a
Problem: Given a graph G(V, E) with edge weights d(i, j), valid bandwidth Multi-Coloring instance since it violates the
find a minimum k and a mapping r from V → {1, ..., k} bandwidth constraint. The example given in Figure 2 is an
such that r(i) = r(j) and |r(i) − r(j)| ≥ d(i, j) for each edge example of a valid instance of the problem.
(i, j) ∈ E.
In this model, the additional constraint that the distance 3. A HEURISTIC APPROACH
between r(i) and r(j) is at least d(i, j) for each edge can
In this section, we discuss a heuristic approach to tackle
be used to model certain applications, such as channel as- generalized graph coloring problems. Since the Bandwidth
signment problem, where edge weights are interpreted as MCP is a generalization of the other three problems, we
the minimum required “separation distance” between two apply the algorithm only to it.
adjacent stations, cells, etc. We will first present the framework of the approach, then
2.3 The Multi-Coloring Problem discuss its components — Greedy Algorithm, SWO and
Tabu Search (TS) respectively.
Problem: Given a graph G(V, E) with node weights
k(i) for each i ∈ V , find a minimum k and subsets S(i) 3.1 Algorithm Framework
⊂ {1, ..., k} such that |S(i)| = k(i) for each i ∈ V and In the algorithm, we modeled solutions as sequences of
S(i) ∩ S(j) = ∅ for each (i, j) ∈ E (where |A| denotes the nodes. Given a sequence of “problem elements”, in the con-
cardinality of set A) text of the SWO approach, we used a greedy algorithm to as-
sign colors to it for a solution and then apply meta-heuristics
In this model, each node can be assigned multiple colors. to adjust these sequences to achieve good or better solutions.
Figure 1 is an example of a valid Multi-Coloring instance Here, the nodes in the graph are the natural candidates to
with k = 8.

934
 k=1
2
Split implies node u has the highest priority);
2 3 c[1..m] records the assigned colors.
2
3 3 2 and the function get original node(u) returns the node v
2
2
3 2 in the original graph such that u is split from v.
2 k=3
2
k=2
Algorithm 1 The Greedy Algorithm which Assigns Colors
for i = 1 to m do
c[i] ← −1
Figure 3: A Instance for Splitting the Nodes in the end for
Graph for i = 1 to m do
f orbidden set ← ∅
Greedy Algorithm u ← p[i]
v ← get original node(u)

Seq
for each node s that adjacent to u do
ce

So
en

uen
lut
io

if c[s]! = −1 then
qu

lut

ion
Se

ce
So

Initial Sequence Best Sequence Final Solution t ← get original node(s)

SWO TS / SA
a ← M ax{0, c[s] − d(v, t) + 1}
b ← c[s] + d(v, t) − 1
f orbidden set ← f orbidden set ∪ [a..b]
Figure 4: The Framework of the Heuristic Approach end if
end for
c[u] ← M in{r, r ∈ N, r ∈ / f orbidden set}
be “problem elements” for the GCP. However, in the Band- end for
width MCP, this is not easily applied because each node will
be assigned several different colors, between which there are
constraints. To deal with this, we split a node with weight 3.3 Squeaky Wheel Optimization
k into k nodes (except k = 1), and treated each new node as “Squeaky Wheel” Optimization (SWO) is a meta-heuristic
the “problem element” in the context of SWO. Hence, node i in which the core is a Construct-Analyze-Prioritize cycle [2,
with weight k becomes a k −clique (a complete subgraph) in 9]. A solution is constructed by a constructor using a
the new graph, with each edge having weight d(i, i) which greedy algorithm where decisions are determined by the pri-
was originally the loop edge weight. This process is illus- orities assigned to the elements of the problem. The ana-
trated in Figure 3. If the original graph had n nodes and lyzer then takes over and is the component that looks for
node Pi had weight k(i), 1 ≤ i ≤ n, then the new graph will those elements that are ”trouble makers” and assigns nu-
have n i=1 k(i) nodes. merical “blame” values to these problem elements i.e. those
When a sequence is given, it will be passed to the greedy elements that contribute to weaknesses in the current solu-
algorithm to generate a solution. The greedy algorithm tion. In [9], blames are assigned to the nodes that use new
is “deterministic” or one-one correspondence, i.e., for two colors, for example. A prioritizer will then modify the se-
identical sequences, resulting solutions are the same. This quence of problem elements and increase the priorities of the
allowed us to exploit meta-heuristic to adjust sequences to trouble makers which then causes the constructor to process
find good or better solutions. them earlier in the next iteration. The cycle repeats until
The algorithm can be divided into two parts. In the first a specified termination condition (number of iterations) is
part, the SWO technique is applied to adjust sequences glob- satisfied.
ally, in particular, through diversification. From this, the The SWO technique has been successful in applications
best solution that SWO finds is passed to a TS heuristic for to Machine Scheduling and Graph Coloring Problems [2, 9].
refinement and better solutions. We adopted TS as the sec- Here we used SWO to generate an initial solution. One rea-
ond meta-heuristics here because of its strength in searching son for this choice is that SWO is fast when compared with
for good solutions in a local search space while avoiding local other meta-heuristics such as TS, Simulated Annealing and
optima. Genetic Algorithms. The other reason is that SWO is able
The greedy algorithm will then be invoked to evaluate the explore the search space more widely and can provide for
sequence so as to determine the number of colors it requires. good diversification in search. It considers both the solu-
The entire framework is summarized in Figure 4. tion space and the priority space where small changes in the
priority space can cause a large change in solution space.
3.2 The Greedy Algorithm This property causes SWO to view the solution space more
The greedy algorithm takes a sequence of “split nodes” globally. The components of SWO, the constructor, the
and assign colors to them greedily. The idea is straightfor- analyzer and the prioritizer, are described as follows:
ward. Following the node sequence, we assign colors one by
• The Constructor: A greedy algorithm is invoked.
one where, for each node, we assign the smallest possible
The priority sequence of the “problem elements” - the
color not used by adjacent earlier nodes. The details of this
split nodes - is passed to the algorithm and a corre-
algorithm is shown as Algorithm 1. Here,
sponding greedy solution constructed.
n is the number of nodes in the original graph;
d(i, j) is the weight of edge (i, j); • The Analyzer: The analyzer will identify the so-
m is the number of nodes after splitting; called “trouble makers” and assign blame values to
p[1..m] is the priority sequence for the m nodes (p[1] = u them.

935
 • The Prioritizer: Once blame has been assigned, the Algorithm 3 The Tabu Search Procedure
prioritizer modifies the previous sequence of problem get initial solution xnow from SWO method
elements. The nodes with higher blame values will be xbest ← xnow
moved forward in the priority sequence while the ones iter ← 0
with small blame values will remain in the back of while iter ≤ max iter do
the sequence. This causes the “trouble makers” to be generate the neighborhood set N (xnow ) by the ex-
handled first by the constructor in the next iteration. change move
evaluate each candidate solution xtrial as f (xtrial ), by
Here, we used a new scheme to calculate the blame values the greedy algorithm
for the implementation of SWO. Assume that, in the cur- xnext ← ∅
rent solution, the maximum color is K. We define “trouble for all xtrial exchanging elements a and b do
makers” as those elements that use colors which are “large if iter > tabu(a ↔ b) and f (xnext ) > f (xtrial ) then
enough”. If the node is assigned color c, then c is “large xnext ← xtrial
enough” if c > α.K, where α is a real number (called a p ← a, q ← b
blame rate) in (0, 1) and close to 1. Problem elements will end if
be assigned a constant blame value b. end for
The SWO algorithm is described in Algorithm 2. tabu(p ↔ q) ← iter + tabu tenure
xnow ← xnext
if f (xbest ) > f (xnow ) then
Algorithm 2 The SWO procedure
xbest ← xnow
Initialize a random priority sequence pri end if
max value ← ∞ iter ← iter + 1
for i = 1 to maximum SWO iterations do end while
invoke the greedy algorithm with the sequence pri
cur value ← the maximum color in the current solution
if cur value < max value then 4. EXPERIMENTAL RESULTS
max value ← cur value
update best solution To test the algorithms, we used the 33 benchmark geomet-
end if ric instances given by Trick which can be found in Computa-
for j=1 to m do tional Symposium Announcement: Graph Coloring and its
blame[j] ← j Generalizations at http://mat.gsia.cmu.edu/COLORING02/.
if c[j] > α ∗ cur value then Points are generated in a 10,000 by 10,000 grid and are con-
blame[j] ← blame[j] + b nected by an edge if they are close enough together. Edge
end if weights are inversely proportional to the distance between
end for nodes and node weights are uniformly generated. GEOMn
sort the sequence pri in ascending order of blame values instances are sparse; GEOMa and GEOMb instances are
end for denser and require fewer colors per node.
We implemented the SWO+TS algorithm using Java and
with the results, we list those from [15] and [11], for experi-
We first ran the SWO for a number of iterations and ments on the same set of instances.
picked up the best solution to be the initial solution of TS, Table 1 gives the parameter settings for the four prob-
which we discuss in the next section. lems. We experimented with different number of restarts
and found that after 10 restarts the marginal improvement
3.4 Tabu Search was small (with a maximum of 2 colors in only two cases out
TS is iterative method designed to help standard local of 33), and beyond 15 restarts, the improvement was negligi-
search methods escape local optima operating through neigh- ble. With more restarts, however, running times increased.
borhood moves that proceed from one solution to another We therefore chose to restart the algorithm 10 times with
at each iteration. In basic TS, some moves are tabu and different (randomized) initial solutions. The comparisons
forbidden unless they lead to desirable outcomes [4]. between the method and the previous two methods is shown
As mentioned earlier, we only considered sequences of in Table 2 where the following notations are used:
problem elements (split nodes). The neighborhood move 1
is an exchange of two nodes in the solution sequence. The • M1 - Method used by Prestwich [15]
move can be denoted a ↔ b for 1 ≤ a, b ≤ m, where m is 2
• M2 - Method used by Lim et al. [11]
the number of nodes in the graph after splitting. A tabu
3
memory is used to forbid a reverse move, within a certain • M3 - The SWO+TS method
number of iterations, to avoid traps at local optima and the
number of iterations for which a particular restriction re- Table 3 and Table 4 give detailed results for the MCP and
mains is given by a tabu tenure. Taking iter to denote the Bandwidth MCP (The detailed results of GCP and Band-
current iteration, after we select the move a ↔ b as the best 1
The benchmark program dfmax(r500.5.b) running time:
one from a number of neighborhood moves (specified as No. 35.21 seconds (user time).
TS moves in the next section), tabu memory is updated as 2
The benchmark program dfmax(r500.5.b) running time:
tabu (a, b) = iter + tabu tenure. The reverse move b ↔ a is 25.32 seconds (user time).
then prevented in the next tabu tenure number of iterations. 3
The benchmark program dfmax(r500.5.b) running time:
The TS procedure is detailed in Algorithm 3. 74.12 seconds (user time).

936
 Parameters Pure Coloring Bandwidth Coloring MCP Bandwidth MCP
Restarts No. 10 10 10 10
SWO Iteration 200 400 400 400
Blame Rate α 0.95 0.95 0.95 0.95
Blame Value b 4 4 4 8
TS Iteration 100 100 200 200
No. of TS Moves 40 40 50 50
TS Tenure 5 5 5 5

Table 1: Parameter Settings

Pure Coloring Bandwidth Coloring MCP Bandwidth MCP

M1 M2 M1 M2 M11 M2 M12 M2
Wins 0 0 0 17 - 0 16 22
Ties 30 31 15 14 - 33 1 11
Loses 3 2 18 2 - 0 0 0
Max Wins 0 0 0 5 - 0 77 11
Avg. Wins 0 0 0 1.53 - 0 20.75 5.23
Max Loses 1 1 11 2 - 0 0 0
Avg. Loses 1.00 1.00 4.61 1.50 - 0 0 0
1 Not presented in [15]

2 Only 17 instances presented in [15]

Table 2: Comparison of M3 with M1 and M2

width Coloring are not presented here due to the space limi- did not increase sharply when instances became larger, and
tation), where k denotes the number of colors and t denotes are comparable with the other two methods. We believe
the running time in seconds. In [15], when there are no this is due to the different heuristics setup. Since we used
results for the MCP, and only partial results for the Band- constant parameters, running times will not change much
width MCP, we write “-” in the tables to denote this. as the sizes vary; however, the running times of the other
The performance of the algorithms is good in all four prob- heuristics were dependant on the instance sizes.
lems and especially so for the Bandwidth MCP. We con-
ducted the experiments using Bandwidth MCP instances 5. CONCLUSION
which are not covered in [15]. Results tied or surpassed all
of the results in [15] and [11]. Although the methods that In this work, we discussed several variations of general-
are applied in [15] are good for GCP and perform well on ized graph coloring problems and proposed a new hybrid
the DIMACS geometric graph instances, the new algorithm SWO with TS technique to solve these. Experiments are
is only weaker in 3 out of 33 cases and for only 1 color each. conducted using benchmark problems and results compared
In the Bandwidth Coloring Problem, results are not as good with those obtained by existing methods. These results show
as [15] although comparable with [11]. that this approach is effective for the problems studied and
We believe that the method in [15] does not work well for provides superior results than the current methods for the
the Bandwidth MCP because there are too many variables Bandwidth MCP.
and constraints to check simultaneously. The backtracker
used there would take a long time to deal with the many 6. REFERENCES
constraints. However, the approach given in [11] and here [1] D. Brelaz. New methods to color the vertices of a
always generates a solution quickly and then improves on it graph. Communications of ACM, 22(4):251–256, 1979.
incrementally. One of the reasons why the method outper- [2] David P. Clements, James M. Crawford, David E.
forms [11] is that TS works well with SWO and is able to Joslin, Geoge L. Nemhauser, Markus E. Puttlitz, and
avoid local optima. Furthermore, we used TS after SWO, Martin W.P. Savelsbergh. Heurstic optimization: A
whereas hill-climbing was implemented in each iteration of hybrid ai/or approach. In Proceedings of the Workshop
the SWO in [11] which results in longer times. In the same on Industrial Constraint-Directed Scheduling, 1997.
amount of time, we were able to run more iterations of SWO [3] Joseph C. Culberson and Feng Luo. Exploring the
to refine the solutions. k-colorable landscape with iterative greedy. Cliques,
It is interesting that in the MCP, we obtained the same Coloring and Satisfiability, Second DIMACS
results as [11] on all the 33 instances. No results are provided Implementation Challenge, 1993.
in [15] for this problem.
[4] Fred Glover and Manuel Laguna. Tabu Search. Kluwer
In terms of running time, the method takes relatively
Acadamic Publishers, 1997.
longer times for small instances, especially for the Color-
ing and Bandwidth Coloring. However, the running times [5] Fred Glover, Mark Parker, and Jennifer Ryan.
Coloring by tabu branch and bound. Cliques, Coloring

937
 and Satisfiability, Second DIMACS Implementation
Challenge, 1993.
[6] A. Hertz and D. de Werra. Using tabu search
techniques for graph coloring. Computing, 39:345–351,
1987.
[7] D. S. Johnson, C. A. Aragon, L. A. Mcgeoch, and
C. Schevon. Optimization by simulated annealing: An
experimental evaluation c part ii (graph coloring and
number partitioning). Operations Research,
31:378–406, 1991.
[8] David S. Johnson and Michael A. Trick (Editors).
Cliques, Coloring and Satisfiability, Second DIMACS
Implementation Challenge. American Mathematical
Society, 1993.
[9] David E. Joslin and David P. Clements. “squeaky
wheel” optimization. In Proceedings of American
Association of Artificial Intelligence National
Conference 1998, pages 340–346, 1998.
[10] Gray Lewandowski and Anne Condon. Expreiments
with parallel graph coloring heuristics and applications
of graph coloring. Cliques, Coloring and Satisfiability,
Second DIMACS Implementation Challenge, 1993.
[11] Andrew Lim, Brian Rodrigues, and Yi Zhu. Crane
scheduling using swo with local search. In Proceedings
of 4th Asia-Pacific Conference on Simulated Evolution
and Learning, 2002.
[12] Andrew Lim, Xingwen Zhang, and Yi Zhu. A hybrid
method for the graph coloring problem and its
generalizations. In 5th Metaheuristics International
Conference (MIC 2003), 2002.
[13] Craig Morgenstern. Distributed coloration
neighborhood search. Cliques, Coloring and
Satisfiability, Second DIMACS Implementation
Challenge, 1993.
[14] Eun-Jon Park, Yong-Hyuk Kim, and Byung-Ro Moon.
Genetic search for fixed channel assignment problem
with limited bandwidth. In Proceedings of Genetic and
Evolutionary Computation Conference, pages
1772–1779, 2002.
[15] Steven Prestwich. Constrained bandwidth
multicoloration neighborhoods. In Proceedings of
Computational Symposium on Graph Coloring and its
Generalizations, 2002.
[16] E. C. Sewell. An improved algorithm for exact graph
coloring. Cliques, Coloring and Satisfiability, Second
DIMACS Implementation Challenge, 1993.

938
 Graph M1 M2 M3 Graph M1 M2 M3
k t k t k t k t k t k t
GEOM20 - - 28 0 28 4 GEOM80 - - 63 0 63 551
GEOM20a - - 30 0 30 3 GEOM80a - - 68 0 68 476
GEOM20b - - 8 0 8 7 GEOM80b - - 25 0 25 111
GEOM30 - - 26 0 26 61 GEOM90 - - 51 0 51 697
GEOM30a - - 40 0 40 99 GEOM90a - - 65 0 65 625
GEOM30b - - 11 0 11 20 GEOM90b - - 28 0 28 135
GEOM40 - - 31 0 31 131 GEOM100 - - 60 0 60 845
GEOM40a - - 46 0 46 138 GEOM100a - - 81 0 81 854
GEOM40b - - 14 0 14 29 GEOM100b - - 30 0 30 156
GEOM50 - - 35 0 35 227 GEOM110 - - 62 0 62 1022
GEOM50a - - 61 0 61 312 GEOM110a - - 91 0 91 1172
GEOM50b - - 17 0 17 46 GEOM110b - - 37 0 37 211
GEOM60 - - 36 0 36 275 GEOM120 - - 64 0 64 1268
GEOM60a - - 65 0 65 391 GEOM120a - - 93 0 93 2349
GEOM60b - - 22 0 22 64 GEOM120b - - 34 0 34 489
GEOM70 - - 44 0 44 374
GEOM70a - - 71 0 71 439
GEOM70b - - 22 0 22 84

Table 3: Experimental Results for MCP

Graph M1 M2 M3 Graph M1 M2 M3
k t k t k t k t k t k t
GEOM20 159 56 149 0 149 176 GEOM80 - - 394 4041 383 2159
GEOM20a 175 145 169 16 169 169 GEOM80a - - 379 677 379 2006
GEOM20b 44 25 44 0 44 25 GEOM80b 152 1380 145 3230 141 417
GEOM30 168 178 160 0 160 241 GEOM90 - - 335 4095 332 2623
GEOM30a 235 64 211 10 209 425 GEOM90a - - 382 10404 377 2587
GEOM30b 79 14 77 0 77 69 GEOM90b - - 157 648 157 489
GEOM40 189 135 167 3 167 496 GEOM100 - - 413 631 404 3283
GEOM40a 260 24 214 358 213 573 GEOM100a - - 462 172 459 3529
GEOM40b 80 94 76 8 74 108 GEOM100b - - 172 4893 170 584
GEOM50 257 96 224 41 224 819 GEOM110 - - 389 577 383 3893
GEOM50a 395 299 326 96 318 125 GEOM110a - - 501 4671 494 4661
GEOM50b 89 94 87 53 87 162 GEOM110b - - 210 12 206 716
GEOM60 279 514 258 46 258 1016 GEOM120 - - 409 1825 402 4317
GEOM60a - - 368 3748 358 1717 GEOM120a - - 564 5335 556 6688
GEOM60b 128 1012 119 300 116 246 GEOM120b - - 201 869 199 1028
GEOM70 310 1019 279 25 273 1458
GEOM70a - - 478 417 469 1987
GEOM70b 133 766 124 136 121 312

Table 4: Experimental Results for Bandwidth MCP

939