On a Routing Problem Within Probabilistic Graphs and its Application to Intermittently Connected Networks
-
Joy Ghosh, Hung Q. Ngo, Seokhoon Yoon, Chunming Qiao
-
INFOCOM 2007
概要だけ
-
問題: 確率的有向グラフからk辺だけ残し、s-t間到達可能確率を最大化せよ
-
色々応用があるよ
-
近似計算: 最短路木を作る+tへの辺を戻す、下限が簡単に計算出来る
-
最適化手法: 最短路を取ってきて貪欲に追加していく
-
それっぽい現実の設定で上手く動きました
まとめ
-
とても通信ネットワーク感があった
-
アルゴリズム的な面白さはほぼ無し
INFOCOM uncertain graphs ルーティング
2017/04/14
最終更新:2017年04月14日 16:38