Fast Approximation Algorithms for the Diameter and Radius of Sparse Graphs
-
Liam Roditty, Virginia Vassilevska Williams
-
In STOC 2013
メモ
-
Aingworth
-
2つの組み合わせ
-
2種類のBFS木の高さの最大値
-
$$ s \in [1,n] $$
-
O(ns^2 + (s+n/s)m)
-
論文の内容
-
ns^2の項を消したい
-
↑高々s頂点のBFS
-
N_s^out(v)を求めないで頑張る
-
乱択を使う
-
3/2近似が高速O(m^{2-\eps})にできると,2と3が区別できる.
-
それから,支配集合問題を帰着できる
-
O(n^{k-\eps})時間で求められる.
-
支配集合問題はSETHからO(n^{k-\eps})は得られないので,
-
O(m^{2-\eps})はだめぽ.
STOC
2013-10-09 23:55:22 (Wed)
最終更新:2013年10月09日 23:55