Maximal Matching Matching グラフG(V,E)においてマッチングMとは隣り合うエッジの組を求めることどの2つのエッジも頂点を共有しない。 Maximal Matching Maximal Matchingとは集合Mに対して現状では集合Vの中でで集合Mの補集合からもはや選ぶエッジが存在し…

(α,ε)近似の定義 がyの(α,ε)近似とはα>1,ε をみたすこと。 考える問題の前提(この部分がDistributed computingの使用) 入力 コミュニケーションネットワーク 定義 各頂点はプロセッサー 各エッジはコミュニケーションのライン グラフは同期しており各ラウン…

Distributed computing vs. sublinear time A reduction and a distributed algorithm. Approximating vertex cover and maximal matching in sublinear time. Introduction sparse graphs(疎グラフ)EがVに対して比較的少ないグラフ dense graphs(密グラフ)E…

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…