Cuthill–McKee algorithm

In the mathematical subfield of matrix theory the Cuthill-McKee algorithm is an algorithm to reduce the bandwidth of sparse symmetric matrices.

Algorithm

Given a symmetric n×n matrix we visualize the matrix as the adjacency matrix of a graph. The Cuthill-McKee algorithm is then a relabeling of the vertices of the graph to reduce the bandwith of the adjacency matrix.

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

First we choose a peripheral vertex x and set R:= ({x}).

Then for i=1,2,.. we iterate the following steps while |R| < n

• Construct the adjacency set A_i of R_i (with R_i the i-th component of R) and exclude the vertices we already have in R

${\displaystyle A_{i}:=\mathrm {Adj(R_{i})} \setminus R}$ 

• Sort A_i with ascending vertex order.

• Append A_i to the Result set R

References

E. Cuthill and J. McKee. Reducing the bandwidth of sparse symmetric matrices In Proc. 24th Nat. Conf. ACM, pages 157-172, 1969.