グラフ同型性判定問題の計算量
スポンサーリンク
概要
- 論文の詳細を見る
本稿では,グラフ同型性判定問題の計算量に関する研究動向を概説する.まず,この判定問題がNP困難ではないと予想させる二つの基本的な根拠を説明し,次に,グラフの様々なクラスに関する同型性判定問題の計算量について解説する.なお,本稿は文献[戸田,グラフ同型性判定問題の計算量,電子情報通信学科論文誌D-I,2002年2月掲載予定]から抜粋したものである.より詳しい内容については,この文献かまたは文献[戸田,グラフ同型性判定問題,日本大学文理学部叢書,冨山房,2001年11月]を参照されたい.
- 一般社団法人電子情報通信学会の論文
- 2002-03-05
著者
関連論文
- 2部グラフの部分クラスに対するGI完全性について
- グラフ同型写像の数え上げ問題に対するアルゴリズムについて
- グラフ同型写像の数え上げ問題に対するアルゴリズムについて
- グラフ同型写像の数え上げ問題に対するアルゴリズム
- 行列集合の自己同型群を求めるための動的計画アルゴリズム
- 小さな単体成分からなるコーダルグラフの自己同型群を求めるためのアルゴリズム
- 区間グラフの認識アルゴリズムについて
- 到達可能性判定問題の計算量について
- 到達可能性判定問題の計算量について(縮約版) (アルゴリズムと計算の理論)
- 数え上げ計算モデルの計算能力について
- 数え上げ計算モデルの計算能力について
- グラフ同型性判定問題の計算量
- グラフ同型性判定問題の計算量(LAシンポジウム(情報基礎理論ワークショップ)論文小特集)
- 解の個数を数えることの複雑さについて : 数え上げ問題の計算量
- 正則言語による論理関数の計算量解析 : 群の上で動作するモノイドプログラムについて (離散的アルゴリズムと計算量)
- 正則言語による論理関数の計算量解析 : 群の上で動作するモノイドプログラムについて
- モノイドプログラムによる論理回路計算量クラスの構造解析