小さな単体成分からなるコーダルグラフの自己同型群を求めるためのアルゴリズム
スポンサーリンク
概要
- 論文の詳細を見る
任意のコーダルグラフは単体成分と呼ばれる部分グラフに一意的に分解されることが知られている。本研究では、この事実に注目することによって、任意のコーダルグラフGに対して、Gの自己同型群がO((c!・n)^<O(1)>)時間で計算可能なことを示す。ここで、cはGの単体成分の最大サイズを表し、nはGの頂点数を表す。
- 社団法人電子情報通信学会の論文
- 2005-06-17
著者
関連論文
- 2部グラフの部分クラスに対するGI完全性について
- グラフ同型写像の数え上げ問題に対するアルゴリズムについて
- グラフ同型写像の数え上げ問題に対するアルゴリズムについて
- グラフ同型写像の数え上げ問題に対するアルゴリズム
- 敷居値関数と通信複雑度について
- グラフの彩色和の近似について
- 行列集合の自己同型群を求めるための動的計画アルゴリズム
- コーダルグラフに関する同型性判定のための単純なアルゴリズム
- 小さな単体成分からなるコーダルグラフの自己同型群を求めるためのアルゴリズム
- 区間グラフの認識アルゴリズムについて
- 到達可能性判定問題の計算量について
- 到達可能性判定問題の計算量について(縮約版) (アルゴリズムと計算の理論)
- 数え上げ計算モデルの計算能力について
- 数え上げ計算モデルの計算能力について
- グラフ同型性判定問題の計算量
- グラフ同型性判定問題の計算量(LAシンポジウム(情報基礎理論ワークショップ)論文小特集)
- 解の個数を数えることの複雑さについて : 数え上げ問題の計算量
- 正則言語による論理関数の計算量解析 : 群の上で動作するモノイドプログラムについて (離散的アルゴリズムと計算量)
- 正則言語による論理関数の計算量解析 : 群の上で動作するモノイドプログラムについて
- モノイドプログラムによる論理回路計算量クラスの構造解析