Cuthill–McKee algorithm

In numerical linear algebra, the Cuthill–McKee algorithm (CM), named after Elizabeth Cuthill and James McKee,[1] 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.

[2] In practice this generally results in less fill-in than the CM ordering when Gaussian elimination is applied.

It starts with a peripheral node and then generates levels

by listing all vertices adjacent to all nodes in

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

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).