About: カットヒル・マキー法

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