In numerical linear algebra, the Cuthill–McKee algorithm (CM), named after Elizabeth Cuthill and James McKee, is an algorithm to permute a sparse matrix that has a symmetric sparsity pattern into a band matrix form with a small bandwidth. The reverse Cuthill–McKee algorithm (RCM) due to Alan George and Joseph Liu is the same algorithm but with the resulting index numbers reversed. In practice this generally results in less fill-in than the CM ordering when Gaussian elimination is applied.
The Cuthill McKee algorithm is a variant of the standard breadth-first search
algorithm used in graph algorithms. It starts with a peripheral node and then
generates levels formula_1 for formula_2 until all nodes
are exhausted. The set formula_3 is created from set formula_4
by listing all vertices adjacent to all nodes in formula_5. These 
nodes are ordered according to predecessors and degree.
Algorithm.
Given a symmetric formula_6 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 bandwidth of the adjacency matrix.
The algorithm produces an ordered "n"-tuple formula_7 of vertices which is the new order of the vertices.
First we choose a peripheral vertex (the vertex with the lowest degree) formula_8 and set formula_9.
Then for formula_10 we iterate the following steps while formula_11
formula_17
In other words, number the vertices according to a particular level structure (computed by breadth-first search) where the vertices in each level are visited in order of their predecessor's numbering from lowest to highest. Where the predecessors are the same, vertices are distinguished by degree (again ordered from lowest to highest).