行列集合の自己同型群を求めるための動的計画アルゴリズム

概要

論文の詳細を見る
X=(U_1∪U_2∪・・・∪U_m∪V,E)を適当なm+1部グラフとする.ただし,U_iとU_jの間には辺は存在しないものとする.その一方で,各辺は適当な全順序集合の要素をラベルとして持ってもよいとする.本稿では,各部集合U_iおよびVを(集合として)固定し,かつ,各辺のラべルを保存するようなXの自己同型群を求める問題を考える.この問題は一般にGl-完全である.従って,現状では,この問題に対して多項式時間アルゴリズムを設計することはとても困難か,あるいは不可能であるとさえ予想される.しかし,各U_iのサイズがある定数以下の場合には(注:Vのサイズは制限しない),多項式時間アルゴリズムが知られている.しかしながら,そのアルゴリズムはcellular algebraと表現論の結果に基づいており,その分,とても込み入ったものになっている.そのため,より単純なアルゴリズムを設計できるか否かが素朴な疑問として生じる.この疑問に関して,本稿では,動的計画法に基づく単純なアルゴリズムを示す.
社団法人電子情報通信学会の論文
2007-05-18