Efficiently Computing k-Edge Connected Components via Graph Decomposition

Efficiently Computing k-Edge Connected Components via Graph Decomposition

  • Lijun Chang, Jeffrey Xu Yu, Lu Qin, Xuemin Lin, Chengfei Liu, Weifa Liang
  • In SIGMOD 2013

メモ

  • K.Oka

問題

  • k枝連結成分
    • 少なくともk本消さないと非連結にならない
    • 大きさk-1のカットがない
  • 極大k枝連結成分
    • 共通部分を持たない
    • 分解できる
  • 応用
    • social networkで似た頂点
    • 可視化

既存手法

  • 最小全域カットしまくる
  • O(n^2(m+n log n))
  • やばお

提案手法

  • 階層的に
  • 同値類
    • v-u間の最小カットがk以上
  • O(hlm)
    • h,l << n
  • キューにぶちこみつつ分解
  • Decompose(g,k)
    • s-t最小カット
    • k以上
      • s,tをマージ
    • k未満
      • S,Tを分割
  • 最小カット: Maximum Adjacency Search
    • 超頑張った

実験結果

  • めっちゃ速くなった
    • ※高速化全部入れると

SIGMOD

2013-10-10 00:05:10 (Thu)

タグ:

SIGMOD
最終更新:2013年10月10日 00:05