グラフの性質検査
Vol.101 No.3pp.253-257
発行日:2018/03/01
Online ISSN:2188-2355
Print ISSN:0913-5693
種別:小特集 グラフアルゴリズムの最先端
専門分野:
キーワード:
グラフ, 定数時間アルゴリズム, 性質検査, 正則性補題,
本文:PDF(539.7KB)>>
あらまし:
性質検査とは,入力が所望の性質を満たしているかどうかを,定数時間で近似的に判定する枠組みである.ここで定数時間とは,入力サイズに依存しない計算時間を指す.グラフに対する性質検査は理論的に非常に豊かな分野であり「どのような性質であれば定数時間で検査できるのか」という問いを軸に大きく発展してきた.本稿ではグラフに対する基礎的な検査アルゴリズムと最先端の成果を紹介する.