Graph connectivity 入力： G = (V,E), n = |V| , m = |E| , bounded degree d*1 グラフはn×dの隣接行列で与えられる 目的： グラフが連結グラフか？ 目的を以下のように変更する Gが連結性にε-closeとは、Gを連結するのに高々εdn本の枝を足せばよいことを言…

Point-set diameter distance matrix -> 距離行列について 配列iと配列jの距離を記述（iとjの距離がDij） >対称行列である（iとjの距離＝jとiの距離） 以下を満たす 入力： m×m距離行列d 目的： 直径 を求める。アルゴリズム を適当に取る d(x,y) が最大とな…

これまでの常識： 問題を解くのに入力すべてを見なければ話にならないとされていた。しかし、一部を見るだけで判断できないか？（モチベーションとしては、生体情報やネットワークグラフのようにそれ自体が巨大な量を持つ問題を解きたい） そんなことが出来…

おおざっぱに言うと、n の増大に対して計算量がどの割合で膨張するのかを示すもの。 計算式の中では一番強いものに引っ張られる。↓は代表的なもの 名前 早さ 概要 数式 例 factorial time slower nのn乗に比例した時間を費やす 巡回セールスマン問題の総当た…