The Strength of Iteration

Given two strings and , whose entries are real numbers, we say that is lexicographically smaller than , written , if , and the smallest , for which is such that .

This leads us to our next algorithm, titled NewSplit.

procedure NewSplit

Input: graph G(V, E); of V

line 1:

for every vertex

line 2:

define a vector , where
is the number of vertices in that are adjacent to x.

line 3:

for every

line 4:

partition into subsets
so that two vertices x and y belong to iff .

line 5:

let be the vector of the vertices in .

line 6:

for every

line 7:

Reorder so that are lexicographically ordered.
Let be the resulting list.

line 8:

Concatenate ; output the total partitioning
and the set of vectors
The following observations are important:

This leads us to a new procedure which iteratively calls NewSplit.

Copyright 2000 Rensselaer Polytechnic Institute. All Rights Reserved.