Cuthill–McKee algorithm

<h2 id="algorithm">Algorithm</h2>
<p>Given a symmetric 
  
    
      
        n
        ×
        n
      
    
    {\displaystyle n\times n}
  
 matrix we visualize the matrix as the <a href="/facts/Adjacency_matrix/jYXNhYGs">adjacency matrix</a> of a <a href="/facts/Graph_(discrete_mathematics)/kw3eIBUe">graph</a>. The Cuthill–McKee algorithm is then a relabeling of the <a href="/facts/Vertex_(graph_theory)/WhlWmL3o">vertices</a> of the graph to reduce the bandwidth of the adjacency matrix.
</p><p>The algorithm produces an ordered <a href="/facts/N-tuple/BI1HIxL8"><i>n</i>-tuple</a> 
  
    
      
        R
      
    
    {\displaystyle R}
  
 of vertices which is the new order of the vertices.
</p><p>First we choose a <a href="/facts/Peripheral_vertex/W0MqKkyE">peripheral vertex</a> (the vertex with the lowest <a href="/facts/Degree_(graph_theory)/LnFFpI8v">degree</a>) 
  
    
      
        x
      
    
    {\displaystyle x}
  
 and set 
  
    
      
        R
        :=
        (
        {
        x
        }
        )
      
    
    {\displaystyle R:=(\{x\})}
  
.
</p><p>Then for 
  
    
      
        i
        =
        1
        ,
        2
        ,
        …
      
    
    {\displaystyle i=1,2,\dots }
  
 we iterate the following steps while 
  
    
      
        
          |
        
        R
        
          |
        
        <
        n
      
    
    {\displaystyle |R|<n}

</p>
<ul><li>Construct the adjacency set 
  
    
      
        
          A
          
            i
          
        
      
    
    {\displaystyle A_{i}}
  
 of 
  
    
      
        
          R
          
            i
          
        
      
    
    {\displaystyle R_{i}}
  
 (with 
  
    
      
        
          R
          
            i
          
        
      
    
    {\displaystyle R_{i}}
  
 the <i>i</i>-th component of 
  
    
      
        R
      
    
    {\displaystyle R}
  
) and exclude the vertices we already have in 
  
    
      
        R
      
    
    {\displaystyle R}
  
</li></ul>

A
          
            i
          
        
        :=
        Adj
        ⁡
        (
        
          R
          
            i
          
        
        )
        ∖
        R
      
    
    {\displaystyle A_{i}:=\operatorname {Adj} (R_{i})\setminus R}

<ul><li>Sort 
  
    
      
        
          A
          
            i
          
        
      
    
    {\displaystyle A_{i}}
  
 ascending by minimum predecessor (the already-visited neighbor with the earliest position in R), and as a tiebreak ascending by <a href="/facts/Degree_(graph_theory)/LnFFpI8v">vertex degree</a>.<a class="footnote-ref" id="fnref:4" href="#fn:4"><sup>4</sup></a></li>
<li>Append 
  
    
      
        
          A
          
            i
          
        
      
    
    {\displaystyle A_{i}}
  
 to the Result set 
  
    
      
        R
      
    
    {\displaystyle R}
  
.</li></ul>
<p>In other words, number the vertices according to a particular <a href="/facts/Level_structure/fgKemoho">level structure</a> (computed by <a href="/facts/Breadth-first_search/2kulDXCx">breadth-first search</a>) where the vertices in each level are visited in order of their predecessor's numbering from lowest to highest. Where the predecessors are the same, vertices are distinguished by degree (again ordered from lowest to highest).
</p>
<h2 id="see-also">See also</h2>
<ul><li><a href="/facts/Graph_bandwidth/ugGo2j8l">Graph bandwidth</a></li>
<li><a href="/facts/Sparse_matrix/FFtN0XjR">Sparse matrix</a></li></ul>

<ul><li><a href="http://www.boost.org/doc/libs/1_37_0/libs/graph/doc/cuthill_mckee_ordering.html">Cuthill–McKee documentation</a> for the <a href="/facts/Boost_C%252B%252B_Libraries/vGLGG51A">Boost C++ Libraries</a>.</li>
<li><a href="http://ciprian-zavoianu.blogspot.com/2009/01/project-bandwidth-reduction.html">A detailed description of the Cuthill–McKee algorithm</a>.</li>
<li><a href="http://www.mathworks.com/help/matlab/ref/symrcm.html">symrcm</a> MATLAB's implementation of RCM.</li>
<li><a href="http://docs.scipy.org/doc/scipy/reference/generated/scipy.sparse.csgraph.reverse_cuthill_mckee.html">reverse_cuthill_mckee</a> RCM routine from <a href="/facts/SciPy/bNcMQGc0">SciPy</a> written in <a href="/facts/Cython/9CyIg2fz">Cython</a>.</li></ul>

<h2 id="references">References</h2>

<ol>
<li id="fn:1"><p>E. Cuthill and J. McKee. Reducing the bandwidth of sparse symmetric matrices In Proc. 24th Nat. Conf. ACM, pages 157–172, 1969. <a href="http://portal.acm.org/citation.cfm?id=805928" target="_blank">http://portal.acm.org/citation.cfm?id=805928</a> <a href="#fnref:1" class="footnote-back-ref">↩</a></p></li>
<li id="fn:2"><p>"Ciprian Zavoianu - weblog: Tutorial: Bandwidth reduction - The CutHill-McKee Algorithm". 15 January 2009. <a href="http://ciprian-zavoianu.blogspot.ch/2009/01/project-bandwidth-reduction.html" target="_blank">http://ciprian-zavoianu.blogspot.ch/2009/01/project-bandwidth-reduction.html</a> <a href="#fnref:2" class="footnote-back-ref">↩</a></p></li>
<li id="fn:3"><p>J. A.  George and J. W-H. Liu, Computer Solution of Large Sparse Positive Definite Systems, Prentice-Hall, 1981 <a href="#fnref:3" class="footnote-back-ref">↩</a></p></li>
<li id="fn:4"><p>The Reverse Cuthill-McKee Algorithm in Distributed-Memory [1], slide 8, 2016 <a href="https://archive.siam.org/meetings/csc16/slides/ariful_azad_CSC16.pdf" target="_blank">https://archive.siam.org/meetings/csc16/slides/ariful_azad_CSC16.pdf</a> <a href="#fnref:4" class="footnote-back-ref">↩</a></p></li>
</ol>

Cuthill–McKee algorithm open-in-new

Cuthill–McKee algorithm