Given a symmetric 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 R of vertices which is the new order of the vertices. First we choose a
peripheral vertex (the vertex with the lowest
degree) x and set R := ( \{ x \}). Then for i = 1,2,\dots we iterate the following steps while |R| • 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 :A_i := \operatorname{Adj}(R_i) \setminus R • Sort 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 A_i to the Result set 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). ==See also==