グラフ同型性判定問題

著者

• 戸田, 誠之助 トダ, セイノスケ

書誌事項

グラフ同型性判定問題

戸田誠之助著

（日本大学文理学部叢書, 2）

日本大学文理学部 , 冨山房 (発売), 2001.11

タイトル読み

グラフ ドウケイセイ ハンテイ モンダイ

注記

参考文献: p119-125

内容説明・目次

内容説明

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

目次

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

「BOOKデータベース」 より

詳細情報

• NII書誌ID(NCID): BA5455575X
• ISBN:
  • 4572999988
• 出版国コード: ja
• タイトル言語コード: jpn
• 本文言語コード: jpn
• 出版地: 東京,東京
• ページ数/冊数: vii, 129p
• 大きさ: 22cm
• 分類:
  • NDC8 : 410.9
  • NDC9 : 410.9
• 件名:
  • BSH : 計算量理論
  • BSH : アルゴリズム
• 親書誌ID:
  • BA54555159