- 著者
-
戸田 誠之助
- 出版者
- 一般社団法人電子情報通信学会
- 雑誌
- 電子情報通信学会技術研究報告. COMP, コンピュテーション (ISSN:09135685)
- 巻号頁・発行日
- vol.101, no.708, pp.15-24, 2002-03-05
- 被引用文献数
-
1
本稿では,グラフ同型性判定問題の計算量に関する研究動向を概説する.まず,この判定問題がNP困難ではないと予想させる二つの基本的な根拠を説明し,次に,グラフの様々なクラスに関する同型性判定問題の計算量について解説する.なお,本稿は文献[戸田,グラフ同型性判定問題の計算量,電子情報通信学科論文誌D-I,2002年2月掲載予定]から抜粋したものである.より詳しい内容については,この文献かまたは文献[戸田,グラフ同型性判定問題,日本大学文理学部叢書,冨山房,2001年11月]を参照されたい.