グラフ同形性問題の解法における完全マッチング問題の利用の効果

概要

論文の詳細を見る
グラフ同形性問題は,一般のグラフについて多項式時間で解けるアルゴリズムがまだ知られていない計算困難な問題の一つである.本論文では,正則グラフを対象とし,グラフ同形性問題の解法への完全マッチング問題の利用について考察を行う.まず,与えられたグラフを層別グラフに再表現し,節点を次数についてラベル付けする.そのラベルにより節点を分類し,グラフのすべての節点における層別グラフについて節点の分類が同じであるかどうかの対応を表にする.その対応表に従い,二つのグラフの節点間の1対1対応を求める.なお,その対応表によりグラフ同形性判定問題を完全マッチング問題として考えることも可能となる.また,対応表は既存の解法にも適用可能であり,それらの効率の向上が期待できる.この方法で実験した結果,(強力な限定操作が行われなくても)実用的な時間で判定が可能であった.また,その結果は現在最速であると考えられている同形性判定プログラムのnautyと比較しても,計算量として遜色ないものであった.
社団法人電子情報通信学会の論文
2002-10-01