コーダルグラフに関する同型性判定のための単純なアルゴリズム

概要

論文の詳細を見る
以前の研究[IEICE Technical Report, COMP 2005-24]において、コーダルグラフの自己同型群を求めるためのアルゴリズムを設計した。また、そのアルゴリズムを利用することによって同型性も判定できることを示した。一方、そのアルゴリズムは群論的手法を多用しており、複雑で時間量の正確な解析も困難であった。そのため、群論的手法を使用することのない、より単純なアルゴリズムを設計できるか否かが素直な疑問として残されていた。そこで、本稿では、コーダルグラフに関する同型性判定問題が、ノードにラベルの付いた根付き木に関する同型性判定問題に還元可能であることを示すことによって、そのような単純なアルゴリズムが設計可能であることを示す。コーダルグラフに関する同型性判定問題はGI完全であるため、本稿で示すアルゴリズムの時間量は一般的には指数的である。しかし、s-成分の最大サイズが相対的に小さいとき(例えば、定数以下であるとき)には多項式的である。
社団法人電子情報通信学会の論文
2006-04-19