Cuthill–McKee algorithm

https://en.wikipedia.org/wiki/Cuthill%E2%80%93McKee_algorithm

• RCM: 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.
• CM is a variant of Breadth First Search
  1. \(R\) is the ordered tuple of vertices we will produce
  2. Choose vertex with lowest degree and add it to \(R\)

  3. Construct adjacency set of \(R_i\) and exclude vertices already in \(R_i\)

     \(A_i = \mathrm{Adj}(R_i) \backslash R_i\)

  4. Sort \(A_i\) ascending by minimum predecessor (the already-visited neighbor with the earliest position in R)
  5. Append \(A_i\) to \(R_i\) and repeat from step 3 until completion.