書誌事項

グラフ同型性判定問題

戸田誠之助著

(日本大学文理学部叢書, 2)

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

タイトル読み

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

大学図書館所蔵 件 / 54

注記

参考文献: p119-125

内容説明・目次

内容説明

本書では、計算量理論とアルゴリズム論の観点から、グラフ同型性判定問題の一端を紹介する。まず、計算量理論の観点から、グラフ同型性判定問題がNP完全とはならないと思われる二つの根拠を紹介する。次に、chordalグラフに関する同型性判定アルゴリズムを解説する。さらに、partial κ‐treeに対する同型性判定アルゴリズムを説明する。

目次

  • 第1章 はじめに(グラフ;置換群 ほか)
  • 第2章 構造的計算複雑さ(計算複雑さの上界;確率型計算量クラスの基本的な性質 ほか)
  • 第3章 Chordalグラフ(標準形根付き木交差モデルの構築;同型性判定アルゴリズム ほか)
  • 第4章 Partial κ‐Tree(木分解の構成;同型性判定アルゴリズム ほか)

「BOOKデータベース」 より

関連文献: 1件中  1-1を表示

詳細情報

  • NII書誌ID(NCID)
    BA5455575X
  • ISBN
    • 4572999988
  • 出版国コード
    ja
  • タイトル言語コード
    jpn
  • 本文言語コード
    jpn
  • 出版地
    東京,東京
  • ページ数/冊数
    vii, 129p
  • 大きさ
    22cm
  • 分類
  • 件名
  • 親書誌ID
ページトップへ