STA Chapter3 part3

Sublinear Time Algorithms

Maximal Matching

Matching

  • グラフG(V,E)においてマッチングMとは隣り合うエッジの組を求めることどの2つのエッジも頂点を共有しない。

Maximal Matching

  • Maximal Matchingとは集合Mに対して現状では集合Vの中でで集合Mの補集合からもはや選ぶエッジが存在しないもの

Maximum Matching

  • Maximum MathcingとはMaximal Matchingの中でエッジの数が最大のもの
Remark

Maximal Matchingの大きさはせいぜいvertex coverの数
次数d以下ならばm/(2d-1)

Greedy Sequential Maximal Matching Algorithm

M \leftarrow \mathbb{0}

  • \forall e = (u,v) \in E
  • u,vともにマッチしていないならeをMに加える

Mを出力
e = (u,v) \in E \: \mathrm{s.t} \: e \notin M　ならばuかvがマッチしているため。

Implementing Oracle to Simulate Greedy

長ーい鎖状になっていたら一個ずつ調べるためθ(i)ステップ必要になる。
解決策は頂点の番号をランダムに振り当てる。すると、このような鎖は存在しなくなる。