グラフ同型性判定問題への招待
Vol.101 No.3pp.267-271
発行日:2018/03/01
Online ISSN:2188-2355
Print ISSN:0913-5693
種別:小特集 グラフアルゴリズムの最先端
専門分野:
キーワード:
グラフ同型性判定問題, GI完全性,
本文:PDF(512.6KB)>>
あらまし:
二つのグラフが「同じ」構造かどうかを判定する問題をグラフ同型性判定問題と呼ぶ.これは,グラフアルゴリズムにおける基本的なものであるにもかかわらず,その計算量が判明していない珍しい問題である.本稿では,この問題に対する既存結果や未解決問題,最近の進展などを紹介する.