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

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

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

• Ordenar ${\displaystyle A_{i}}$ siguiendo una ordenación ascendente de los vértices.
• Añadir ${\displaystyle 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.