あらまし

グラフ同型性判定問題への招待

大舘 陽太 

Vol.101 No.3pp.267-271

発行日:2018/03/01

Online ISSN:2188-2355

Print ISSN:0913-5693

種別:小特集 グラフアルゴリズムの最先端

専門分野:

キーワード:
グラフ同型性判定問題GI完全性

本文:PDF(512.6KB)

あらまし:
二つのグラフが「同じ」構造かどうかを判定する問題をグラフ同型性判定問題と呼ぶ.これは,グラフアルゴリズムにおける基本的なものであるにもかかわらず,その計算量が判明していない珍しい問題である.本稿では,この問題に対する既存結果や未解決問題,最近の進展などを紹介する.

ログイン

 > 

パスワードを忘れた場合は

メニュー

Online ISSN:2188-2355