グラフ同型性判定問題(日本大学文理学部叢書) [全集叢書]

グラフ同型性判定問題(日本大学文理学部叢書) [全集叢書] の 商品概要

• 要旨（「BOOK」データベースより）

  本書では、計算量理論とアルゴリズム論の観点から、グラフ同型性判定問題の一端を紹介する。まず、計算量理論の観点から、グラフ同型性判定問題がＮＰ完全とはならないと思われる二つの根拠を紹介する。次に、ｃｈｏｒｄａｌグラフに関する同型性判定アルゴリズムを解説する。さらに、ｐａｒｔｉａｌ　κ‐ｔｒｅｅに対する同型性判定アルゴリズムを説明する。

• 目次（「BOOK」データベースより）

  第１章　はじめに（グラフ
  置換群　ほか）
  第２章　構造的計算複雑さ（計算複雑さの上界
  確率型計算量クラスの基本的な性質　ほか）
  第３章　Ｃｈｏｒｄａｌグラフ（標準形根付き木交差モデルの構築
  同型性判定アルゴリズム　ほか）
  第４章　Ｐａｒｔｉａｌ　κ‐Ｔｒｅｅ（木分解の構成
  同型性判定アルゴリズム　ほか）

• 著者紹介（「BOOK著者紹介情報」より）（本データはこの書籍が刊行された当時に掲載されていたものです）

  戸田 誠之助(トダ セイノスケ)
  １９５９年生まれ。現在、日本大学文理学部情報システム解析学科教授。理学博士。１９８４年、電気通信大学大学院修士課程修了、以降、国文学研究資料館研究情報部、電気通信大学情報工学科、日本大学文理学部応用数学科を経て現在に至る。１９９８年、数え上げ問題の計算量に関する研究によりＡＣＭ‐ＳＩＧＡＣＴ／ＥＡＴＣＳ　Ｇ¨ｏｄｅｌ　Ｐｒｉｚｅ受賞。同年、日本ＩＢＭ科学賞受賞。１９９９年日本大学文理学部賞受賞。２０００年、電気通信大学同窓会賞受賞。専門は情報科学の基礎理論、特に、計算量理論

グラフ同型性判定問題(日本大学文理学部叢書) [全集叢書] の商品スペック