Fast Approximation Algorithms for the Diameter and Radius of Sparse Graphs

Fast Approximation Algorithms for the Diameter and Radius of Sparse Graphs

  • Liam Roditty, Virginia Vassilevska Williams
  • In STOC 2013

メモ

  • Y.Yano
  • 直径2近似O(n+m)
    • BFSして最大の高さ
  • additive approximation
  • 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)

タグ:

STOC
最終更新:2013年10月09日 23:55