Cuthill–McKee algorithm: Difference between revisions

Revision as of 23:29, 19 December 2016

Revision as of 16:24, 16 January 2017

Line 17:

Given a symmetric <math>n\times n</math> matrix we visualize the matrix as the [[adjacency matrix]] of a [[Graph (discrete mathematics)|graph]]. The Cuthill–McKee algorithm is then a relabeling of the [[vertex (graph theory)|vertices]] of the graph to reduce the bandwidth of the adjacency matrix.

The algorithm produces an ordered [[n-tuple|''n''-tuple]] ''<math>R''</math> 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]]) ''<math>x''</math> and set ''<math>R'' := ( \{'' x'' \})</math>.

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

*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''