距離幅がバウンドされているグラフに対するグラフ同型性判定問題
スポンサーリンク
概要
- 論文の詳細を見る
本稿において、木幅、次数、バンド幅がバウンドされたグラフに対するグラフ同型性判定問題について述べる。木幅、次数、バンド幅がバウンドされたグラフに対するグラフ同型性判定問題に対するO(n^c)時間のアルゴリズムが知られている。しかしながら、その定数cはそのバウンドに依存している。我々は、距離幅という新しいパラメータを考え、距離幅がバウンドされているグラフに対するグラフ同型性判定問題に対し、O(n^2)時間のアルゴリズムを紹介する。また木距離幅という新しいパラメータを考え、木距離幅がバウンドされているグラフに対するグラフ同型性判定問題に対し、O(n^3)時間のアルゴリズムを紹介する。
- 社団法人電子情報通信学会の論文
- 1997-05-30