Algoritmo de Cuthill-McKee

En el subcampo matemático de la teoría de matrices, el algoritmo de Cuthill-McKee es un algoritmo para reducir el ancho de banda de una matriz simétrica dispersa. El algoritmo invertido de Cuthill-McKee (RCM, por las siglas inglesas Reverse Cuthill-McKee) es el mismo algoritmo pero con los índices resultantes invertidos. En el ámbito práctico, emplear este último es generalmente una mejor solución.

Algoritmo

Dada una matriz simétrica n×n, se visualiza como la matriz de adyacencia de un grafo. El algoritmo de Cuthill-McKee es entonces una renumeración de los vértices del grafo con el objetivo de reducir el ancho de banda de su matriz de adyacencia.

El algoritmo produce una n-tupla ordenada R de vértices, que es el nuevo orden de los vértices.

Primero, se elige un vértice periférico x y se realiza la asignación R := ({x}).

A continuación, para i = 1, 2, ... se iteran las próximas instrucciones mientras |R| < n

• Construír el conjunto de adyacencia $A_{i}$ de $R_{i}$ (siendo $R_{i}$ el i-ésimo componente de R) excluyendo aquellos vértices que ya estuvieran en R.

$A_{i}:=\operatorname {Ady} (R_{i})\setminus R$

• Ordenar $A_{i}$ siguiendo una ordenación ascendente de los vértices.
• Añadir $A_{i}$ al conjunto resultado R.

En otras palabras, numerar los vértices de acuerdo a una particular búsqueda en anchura transversal, donde los vértices vecinos son visitados en orden de menor a mayor.

Referencias

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

Enlaces externos

• Documentación del algoritmo de Cuthill–McKee para la Biblioteca Boost.