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…