Cuthill–McKee algorithm: Difference between revisions

Revision as of 00:01, 14 September 2012

Revision as of 23:41, 11 February 2013

Line 20:

The algorithm produces an ordered [[n-tuple|''n''-tuple]] ''R'' of vertices which is the new order of the vertices.

First we choose a [[peripheral vertex]] (the vertex with the lowest [[Degree (graph theory)|degree]]) ''x'' and set ''R'' := ({''x''}).

Then for <math>i = 1,2,\dots</math> we iterate the following steps while |''R''| < ''n''

Line 26:

*Construct the adjacency set <math>A_i</math> of <math>R_i</math> (with <math>R_i</math> the ''i''-th component of ''R'') and exclude the vertices we already have in ''R''

:<math>A_i := \operatorname{Adj}(R_i) \setminus R</math>

*Sort <math>A_i</math> with ascending vertex order ([[Degree (graph theory)|vertex degree]]).

*Append <math>A_i</math> to the Result set ''R''.