グラフ同型性判定問題の計算量(<小特集>LAシンポジウム(情報基礎理論ワークショップ)論文小特集)
スポンサーリンク
概要
- 論文の詳細を見る
本論文では,グラフ同型性判定問題の計算量に関してこれまでの研究動向を解説する.まず,この判定問題がNP困難ではないと予想させる二つの基本的な根拠を説明する.次に,グラフの様々なクラスに関する同型性判定問題の計算量について解説する.最後に,多項式時間アルゴリズムの典型として,Luksによって設計された3次グラフに対する同型性判定アルゴリズムと,名古屋によって設計されたchordalグラフに対する同型性判定アルゴリズムについて詳しく解説する.
- 一般社団法人電子情報通信学会の論文
- 2002-02-01
著者
関連論文
- 2部グラフの部分クラスに対するGI完全性について
- グラフ同型写像の数え上げ問題に対するアルゴリズムについて
- グラフ同型写像の数え上げ問題に対するアルゴリズムについて
- グラフ同型写像の数え上げ問題に対するアルゴリズム
- 行列集合の自己同型群を求めるための動的計画アルゴリズム
- 小さな単体成分からなるコーダルグラフの自己同型群を求めるためのアルゴリズム
- 区間グラフの認識アルゴリズムについて
- 到達可能性判定問題の計算量について
- 到達可能性判定問題の計算量について(縮約版) (アルゴリズムと計算の理論)
- 数え上げ計算モデルの計算能力について
- 数え上げ計算モデルの計算能力について
- グラフ同型性判定問題の計算量
- グラフ同型性判定問題の計算量(LAシンポジウム(情報基礎理論ワークショップ)論文小特集)
- 解の個数を数えることの複雑さについて : 数え上げ問題の計算量
- 正則言語による論理関数の計算量解析 : 群の上で動作するモノイドプログラムについて (離散的アルゴリズムと計算量)
- 正則言語による論理関数の計算量解析 : 群の上で動作するモノイドプログラムについて
- モノイドプログラムによる論理回路計算量クラスの構造解析