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枝連結成分
-
少なくともk本消さないと非連結にならない
-
大きさk-1のカットがない
-
極大k枝連結成分
-
応用
既存手法
-
最小全域カットしまくる
-
O(n^2(m+n log n))
-
やばお
提案手法
-
階層的に
-
同値類
-
O(hlm)
-
キューにぶちこみつつ分解
-
Decompose(g,k)
-
最小カット: Maximum Adjacency Search
実験結果
SIGMOD
2013-10-10 00:05:10 (Thu)
最終更新:2013年10月10日 00:05