グラフ同型性判定問題
Author(s)
Bibliographic Information
グラフ同型性判定問題
(日本大学文理学部叢書, 2)
日本大学文理学部 , 冨山房 (発売), 2001.11
- Title Transcription
-
グラフ ドウケイセイ ハンテイ モンダイ
Available at 54 libraries
  Aomori
  Iwate
  Miyagi
  Akita
  Yamagata
  Fukushima
  Ibaraki
  Tochigi
  Gunma
  Saitama
  Chiba
  Tokyo
  Kanagawa
  Niigata
  Toyama
  Ishikawa
  Fukui
  Yamanashi
  Nagano
  Gifu
  Shizuoka
  Aichi
  Mie
  Shiga
  Kyoto
  Osaka
  Hyogo
  Nara
  Wakayama
  Tottori
  Shimane
  Okayama
  Hiroshima
  Yamaguchi
  Tokushima
  Kagawa
  Ehime
  Kochi
  Fukuoka
  Saga
  Nagasaki
  Kumamoto
  Oita
  Miyazaki
  Kagoshima
  Okinawa
  Korea
  China
  Thailand
  United Kingdom
  Germany
  Switzerland
  France
  Belgium
  Netherlands
  Sweden
  Norway
  United States of America
Search this Book/Journal
Note
参考文献: p119-125
Description and Table of Contents
Description
本書では、計算量理論とアルゴリズム論の観点から、グラフ同型性判定問題の一端を紹介する。まず、計算量理論の観点から、グラフ同型性判定問題がNP完全とはならないと思われる二つの根拠を紹介する。次に、chordalグラフに関する同型性判定アルゴリズムを解説する。さらに、partial κ‐treeに対する同型性判定アルゴリズムを説明する。
Table of Contents
- 第1章 はじめに(グラフ;置換群 ほか)
- 第2章 構造的計算複雑さ(計算複雑さの上界;確率型計算量クラスの基本的な性質 ほか)
- 第3章 Chordalグラフ(標準形根付き木交差モデルの構築;同型性判定アルゴリズム ほか)
- 第4章 Partial κ‐Tree(木分解の構成;同型性判定アルゴリズム ほか)
by "BOOK database"