Refining Procedure

procedure Refine

Input: graph ; partitioning of

line 1:

set

line 2:

repeat

line 3:

NewSplit

line 4:

until (NewSplit )

Example

Let us again consider the leftmost graph G from before and the trivial partitioning π0 of G, which has just one partition: the whole vertex set.

The first iteration of the repeat-loop in Refine applies NewSplit to ; it is equivalent to applying Split.  The result is shown in Step 1.  The next iteration of NewSplit is then applied to ; the vectors computed are This yields Step 2-1.  The reordering produces Step 2-2.  Finally, the last iteration of Refine produces the partitioning with every partition of size 1.  This in fact mean that the problem is completely solved; for every graph isomorphic to our graph G, Refine will construct a partitioning which has all partitions of size 1.  This is an ideal situation.

Application of Refine

Copyright 2000 Rensselaer Polytechnic Institute. All Rights Reserved.