内容説明
本書では、計算量理論とアルゴリズム論の観点から、グラフ同型性判定問題の一端を紹介する。まず、計算量理論の観点から、グラフ同型性判定問題がＮＰ完全とはならないと思われる二つの根拠を紹介する。次に、ｃｈｏｒｄａｌグラフに関する同型性判定アルゴリズムを解説する。さらに、ｐａｒｔｉａｌ κ‐ｔｒｅｅに対する同型性判定アルゴリズムを説明する。
目次
第１章 はじめに（グラフ；置換群 ほか）
第２章 構造的計算複雑さ（計算複雑さの上界；確率型計算量クラスの基本的な性質 ほか）
第３章 Ｃｈｏｒｄａｌグラフ（標準形根付き木交差モデルの構築；同型性判定アルゴリズム ほか）
第４章 Ｐａｒｔｉａｌ κ‐Ｔｒｅｅ（木分解の構成；同型性判定アルゴリズム ほか）
著者等紹介
戸田誠之助［トダセイノスケ］
１９５９年生まれ。現在、日本大学文理学部情報システム解析学科教授。理学博士。１９８４年、電気通信大学大学院修士課程修了、以降、国文学研究資料館研究情報部、電気通信大学情報工学科、日本大学文理学部応用数学科を経て現在に至る。１９９８年、数え上げ問題の計算量に関する研究によりＡＣＭ‐ＳＩＧＡＣＴ／ＥＡＴＣＳ Ｇ¨ｏｄｅｌ Ｐｒｉｚｅ受賞。同年、日本ＩＢＭ科学賞受賞。１９９９年日本大学文理学部賞受賞。２０００年、電気通信大学同窓会賞受賞。専門は情報科学の基礎理論、特に、計算量理論
※書籍に掲載されている著者及び編者、訳者、監修者、イラストレーターなどの紹介情報です。
感想・レビュー
※以下の感想・レビューは、株式会社ブックウォーカーの提供する「読書メーター」によるものです。
U-tan
1
Diestel を読まなければならない．2015/04/03
kinaba
0
特に前半勉強になった2009/09/06
