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:
- Procedure Split can be viewed as an application of
NewSplit to graph G and the trivial partitioning π
0 which has just one partition: the vertex set V(G).
- Procedure NewSplit can be used iteratively, since the
output of the procedure is of the same nature as the input: a partitioning
of the vertex set of the graph.
This leads us to a new procedure which iteratively calls
NewSplit.
Copyright
2000
Rensselaer Polytechnic Institute. All Rights Reserved.