Cuthill–McKee algorithm

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 ${\displaystyle R_i}$ for ${\displaystyle i=1,2,..}$ until all nodes are exhausted. The set ${\displaystyle R_{i+1}}$ is created from set ${\displaystyle R_i}$ by listing all vertices adjacent to all nodes in ${\displaystyle R_i}$. These nodes are ordered according to predecessors and degree.

Algorithm

Given a symmetric ${\displaystyle n\times 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 bandwidth of the adjacency matrix.

The algorithm produces an ordered n-tuple ${\displaystyle R}$ of vertices which is the new order of the vertices.

First we choose a peripheral vertex (the vertex with the lowest degree) ${\displaystyle x}$ and set ${\displaystyle R:=(\{x\})}$.

Then for ${\displaystyle i=1,2,\dots }$ we iterate the following steps while ${\displaystyle |R|<n}$

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

${\displaystyle A_i:=\mathrm{Adj}(R_i)\setminus R}$

• Sort ${\displaystyle A_i}$ ascending by minimum predecessor (the already-visited neighbor with the earliest position in R), and as a tiebreak ascending by vertex degree.
• Append ${\displaystyle A_i}$ to the Result set ${\displaystyle R}$.

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