Cuthill-McKee algorithm

The Cuthill-McKee algorithm, named after Elizabeth Cuthill and James McKee, is used in numerical linear algebra to permute a sparse matrix that has a symmetric sparsity pattern into a band matrix form with a small bandwidth. It is a variant of the standard breadth-first search used in graph algorithms: it starts from a peripheral node and generates successive levels of vertices until all nodes are exhausted, ordering the nodes within each level by their predecessors and degree. The reverse Cuthill-McKee algorithm, due to Alan George and Joseph Liu, is the same procedure with the resulting index numbers reversed, and in practice it generally produces less fill-in than the original ordering when Gaussian elimination is applied.