Estimating the Weight of the Minimum Spanning Tree Spanning Tree(以下st) あるグラフの全ての頂点とそのグラフを構成する辺の一部分のみで構成される木のこと 問題設定 入力 無向グラフG(V,E) 制限d 各エッジ(i,j)は整数の重みをもつ隣接知ると出グラフ…

Estimating the Number of Connected Components Connected Components(連結成分,以下c.cと書く) c.c内の任意の二点間を結ぶパスが存在する。 異なるc.c間にはいかなるパスも存在しない。 問題設定 入力 無向グラフG(V,E) 制限d 目標 c.cの数をcとしたとき、…

Sublinear Time Algorithms Lecture2 やる内容 Chernoff bound Estimating the number of connected components Estimating the weight of the minimum spanning tree Chernoff bound Let be m independent identically distributed random variables such t…