Polynomial-Time Algorithm for Finding Densest Subgraphs in Uncertain Graphs
-
Zhaonian Zou
-
Workshop on Mining and Learning with Graphs
概要だけ
-
Uncertain graphから期待密度最大の部分グラフ抽出
-
問題1: 制約無し
-
(期待密度)=(∑各辺の確率)
-
各辺の周辺確率が分かっていれば良い
-
ただの最密部分グラフ
-
$$ \mathcal{O}(nm\log(n^2/m)) $$時間
-
問題2: 頂点集合Rを含む
-
別にUncertain graph特有の何かではない
-
parametric maximum flowで同じ計算時間
まとめ
MLG uncertain graphs 最密部分グラフ
2016/10/17
最終更新:2016年10月17日 19:59