グラフ同型性判定問題
Author(s)
Bibliographic Information
グラフ同型性判定問題
（日本大学文理学部叢書, 2）
日本大学文理学部 , 冨山房 (発売), 2001.11
- Title Transcription
-
グラフ ドウケイセイ ハンテイ モンダイ
Available at / 54 libraries
-
No Libraries matched.
- Remove all filters.
Search this Book/Journal
Note
参考文献: p119-125
Description and Table of Contents
Description
本書では、計算量理論とアルゴリズム論の観点から、グラフ同型性判定問題の一端を紹介する。まず、計算量理論の観点から、グラフ同型性判定問題がＮＰ完全とはならないと思われる二つの根拠を紹介する。次に、ｃｈｏｒｄａｌグラフに関する同型性判定アルゴリズムを解説する。さらに、ｐａｒｔｉａｌ κ‐ｔｒｅｅに対する同型性判定アルゴリズムを説明する。
Table of Contents
- 第１章 はじめに（グラフ；置換群 ほか）
- 第２章 構造的計算複雑さ（計算複雑さの上界；確率型計算量クラスの基本的な性質 ほか）
- 第３章 Ｃｈｏｒｄａｌグラフ（標準形根付き木交差モデルの構築；同型性判定アルゴリズム ほか）
- 第４章 Ｐａｒｔｉａｌ κ‐Ｔｒｅｅ（木分解の構成；同型性判定アルゴリズム ほか）
by "BOOK database"
