「Polynomial-Time Algorithm for Finding Densest Subgraphs in Uncertain Graphs」の編集履歴（バックアップ）一覧はこちら

「Polynomial-Time Algorithm for Finding Densest Subgraphs in Uncertain Graphs」(2016/10/17 (月) 19:59:08) の最新版変更点

追加された行は緑色になります。

削除された行は赤色になります。

* 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で同じ計算時間

* まとめ
- 最初は期待してたが，スーン…ってなった．

&tags()

2016/10/17