あらまし

グラフの性質検査

田　悠一 

Vol.101 No.3pp.253-257

発行日:2018/03/01

Online ISSN:2188-2355

Print ISSN:0913-5693

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

専門分野:

キーワード:
グラフ, 定数時間アルゴリズム, 性質検査, 正則性補題, 

本文:PDF(539.7KB)>>

記事を購入

あらまし:
性質検査とは，入力が所望の性質を満たしているかどうかを，定数時間で近似的に判定する枠組みである．ここで定数時間とは，入力サイズに依存しない計算時間を指す．グラフに対する性質検査は理論的に非常に豊かな分野であり「どのような性質であれば定数時間で検査できるのか」という問いを軸に大きく発展してきた．本稿ではグラフに対する基礎的な検査アルゴリズムと最先端の成果を紹介する．

ログイン

 > 

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

メニュー

Online ISSN:2188-2355

…ジュニア会員・学生員に
　お勧めの記事