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 de (siendo el i-ésimo componente de R) excluyendo aquellos vértices que ya estuvieran en R.
Ordenar siguiendo una ordenación ascendente de los vértices. Añadir 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.
Categoría:Matrices Categoría:Algoritmos de grafos