On a Routing Problem Within Probabilistic Graphs ...

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