cuthill-mckee algorithm

In the mathematical subfield of matrix theory the Cuthill-McKee algorithm is an algorithm to reduce the bandwidth of sparse symmetric matrices.

Algorithm

Given a symmetric n×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 x and set R:= ({x}). Then for i=1,2,.. we iterate the following steps while |R| < n

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 := \mathrm{Adj(R_i)} \setminus R

Sort A_i with ascending vertex order.

Append A_i to the Result set R

References

E. Cuthill and J. McKee. Reducing the bandwidth of sparse symmetric matrices In Proc. 24th Nat. Conf. ACM, pages 157-172, 1969.

<< Previous

Word Browser

Next >>

edelweiss (band)
junie morrison
sister grove trail
linda shider
jonathan coachman
trindade (island)
grand puba
august cieszkowski
maxi priest
taiko: drum master
white oak lake state park

indigenous church mission theory
shabba ranks
erkrath
aghabullogue
stefan drzewiecki
tuesday night music club
fogo
allihies
melbu
ballaghaderreen
lund

muriqui
ballincollig
brava, cape verde
the motorcycle diaries
mike bucci
ballinhassig
cergy pontoise
testicular size
ballycotton
laser scalpel
julia lathrop

ballygarvan
robert patrick casey, jr.
ballyheigue
johan helmich roman
ballylickey
miami airport (tri rail station)
pat jabbar
buttevant
brenda bennett
castletownbere
mathew ector