9.21

Cuthill–McKee / Reverse-Cuthill–McKee heuristic
1. Input: undirected graph G=(V,E) with n=|V|.
2. Let π be the final permutation list (initially empty); let all vertices be unvisited.
3. While an unvisited vertex exists:
  a. Pick a start vertex s of minimum degree among the unvisited ones. (If several exist, take the one with the smallest id.)
  b. Do a BFS beginning with s: when a vertex u is taken from the queue, append it to π; push all still-unvisited neighbours of u, but sorted by non-decreasing degree.
4. Reverse π (this simple trick very often lowers the bandwidth; omitting the reversal yields the original CM order).
5. Compute the bandwidth b = max(|pos(u) − pos(v)| for (u,v) in E), where pos(x) is the index of x in π (1-based).

Pseudocode
def rcm(G):
n = len(G) # adjacency list
unvisited = set(G.keys())
π = []
while unvisited:
s = min(unvisited, key=lambda v: (len(G[v]), v))
queue = [s]
unvisited.remove(s)
for u in queue: # plain for-loop acts as FIFO
π.append(u)
nbrs = [w for w in G[u] if w in unvisited]
nbrs.sort(key=lambda w: (len(G[w]), w))
for w in nbrs:
unvisited.remove(w)
queue.extend(nbrs)
π.reverse() # RCM step
pos = {v:i for i,v in enumerate(π,1)}
b = max(abs(pos[u]-pos[v]) for u in G for v in G[u])
return π, b


Correctness (heuristic): CM pushes low-degree vertices outward and keeps densely connected vertices close in the ordering; reversing places the low-degree “peripheral” vertices at both ends, shrinking the maximum edge span. Although optimal bandwidth is NP-hard to obtain, this strategy is empirically near-optimal for sparse and banded matrices.

Complexity: every vertex and edge is processed once; sorting neighbours costs Σ deg(u)·log deg(u) ≤ O(E log Δ), where Δ is the maximum degree. Hence total time O(E log Δ) and memory O(V+E).

Output: permutation π (index → vertex) together with its bandwidth b; both can be used to permute the adjacency matrix so that all non-zero entries lie inside the first b sub- and super-diagonals.

Back to Chapter 9