Added to Favorites

Popular Searches

Definitions

Nearby Words

In the mathematical subfield of matrix theory the Cuthill–McKee algorithm is an algorithm to reduce the bandwidth of sparse symmetric matrices. The reverse Cuthill–McKee algorithm (RCM) is the same algorithm but with the resulting index numbers reversed. In practice this is generally a better solution.
## Algorithm

## References

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

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\; :=\; operatorname\{Adj\}(R\_i)\; setminus\; R$

- Sort $A\_i$ with ascending vertex order.
- Append $A\_i$ to the Result set R.

In other words, number the vertices according to a particular breadth-first traversal where neighboring vertices are visited in order from lowest to highest vertex order.

Wikipedia, the free encyclopedia © 2001-2006 Wikipedia contributors (Disclaimer)

This article is licensed under the GNU Free Documentation License.

Last updated on Sunday April 13, 2008 at 14:29:06 PDT (GMT -0700)

View this article at Wikipedia.org - Edit this article at Wikipedia.org - Donate to the Wikimedia Foundation

This article is licensed under the GNU Free Documentation License.

Last updated on Sunday April 13, 2008 at 14:29:06 PDT (GMT -0700)

View this article at Wikipedia.org - Edit this article at Wikipedia.org - Donate to the Wikimedia Foundation

Copyright © 2014 Dictionary.com, LLC. All rights reserved.