application of the
bnd
bipartitioning method to the band graph leads to
a situation where both anchor vertices are placed in the same part.
width=
val
Set the width of the band graph. All graph vertices that are at a distance
less than or equal to
val
from any frontier vertex are kept in the band
graph.
d
Diffusion method. This method, presented in [42], flows two kinds of antag-
onistic liquids, scotch and anti-scotch, from two source vertices, and sets the
new frontier as the limit between vertices which contain scotch and the ones
which contain anti-scotch. Because selecting the source vertices is essential
to the obtainment of useful results, this method has been hard-coded so that
the two source vertices are the two vertices of highest indices, since in the
band method these are the anchor vertices which represent all of the removed
vertices of each part. Therefore, this method must be used on band graphs
only, or on specifically crafted graphs. Applying it to any other graphs is
very likely to lead to extremely poor results. The parameters of the diffusion
bipartitioning method are listed below.
dif=
rat
Fraction of liquid which is diffused to neighbor vertices at each pass. To
achieve convergence, the sum of the
dif
and
rem
parameters must be
equal to 1, but in order to speed-up the diffusion process, other combi-
nations of higher sum can be tried. In this case, the number of passes
must be kept low, to avoid numerical overflows which would make the
results useless.
pass=
nbr
Set the number of diffusion sweeps performed by the algorithm. This
number depends on the width of the band graph to which the diffusion
method is applied. Useful values range from 30 to 500 according to
chosen
dif
and
rem
coefficients.
rem=
rat
Fraction of liquid which remains on vertices at each pass. See above.
f
Fiduccia-Mattheyses method. The parameters of the Fiduccia-Mattheyses
method are listed below.
bal=
rat
Set the maximum weight imbalance ratio to the given fraction of the
subgraph vertex weight. Common values are around 0
.
01, that is, one
percent.
move=
nbr
Maximum number of hill-climbing moves that can be performed before a
pass ends. During each of its passes, the Fiduccia-Mattheyses algorithm
repeatedly swaps vertices between the two parts so as to minimize the
cost function. A pass completes either when all of the vertices have been
moved once, or if too many swaps that do not decrease the value of the
cost function have been performed. Setting this value to zero turns the
Fiduccia-Mattheyses algorithm into a gradient-like method, which may
be used to quickly refine partitions during the uncoarsening phase of the
multi-level method.
61
