カットヒル・マキー法

行列を扱う数学分野において、カットヒル・マキー法 (カットヒル・マッキー並べ替えとも、Cuthill–McKee algorithm, CM) は Elizabeth Cuthill J. McKee に因んで名付けられた、対称なパターンを持つ疎行列をの小さいの形に並び替えるアルゴリズムである。同じアルゴリズムだが、指数が逆順となる、逆カットヒル・マキー法 (Reverse Cuthill–McKee algorithm ,RCM) と呼ばれる Alan George によるアルゴリズムもある。実用上、ガウシアン除去と共に適用した場合は CM 並べ替えよりもフィルインが少くなることが知られている。カットヒル・マキー法 はグラフ理論上で標準的に用いられる、幅優先探索アルゴリズムの一変種である。 <math>R_i</math> (<math>i=1, 2,..</math> )を、外縁ノードから始め、全てのノードを被覆するまで生成する。集合 <math> R_ </math> は集合 <math> R_i</math> 内の全ノードの隣接頂点から生成される。 これらのノードは次数が昇順になるよう並べられる。この点のみが幅優先探索アルゴリズムとの違いである。