定数コストの横断辺を持つ梯子状ネットワークの最適化
スポンサーリンク
概要
- 論文の詳細を見る
利己的ルーティングの下では,ネットワークの一部のリンクを削除することでナッシュフローのコストが減少する場合がある.一般のネットワークにおいてそのようなリンクを特定するネットワーク最適化問題は NP 困難である.さらに,ナッシュフローのコストを多項式時間で最小化できるような自明でない十分条件でさえも知られていない.本報告では定数コストの横断辺を持つ n ノードの梯子状ネットワークに対して,動的計画法を用いて最小コストのナッシュフローを持つ全域部分ネットワークを求める O(n3) 時間アルゴリズムを示す.
- 2012-10-26
著者
関連論文
- リングにおける競合的オンラインデータ移動アルゴリズム
- 分割子に基づく高次元格子への小さい辺負荷を持つグラフ埋め込み(グラフ,ペトリネット,ニューラルネット,及び一般)
- 分割子に基づく高次元格子への小さい辺負荷を持つグラフ埋め込み(グラフ,ペトリネット,ニューラルネット,及び一般)
- グラフの幅2の真のパス分解を求める効率的アルゴリズム
- グラフの格子への辺負荷最小埋め込みの計算複雑度について
- グラフのハイパーキューブへの辺負荷最小の埋め込み
- 3点上の最適なオンラインページ移動
- リングネットワークにおけるファイル配置問題について
- グラフを梯子へ最小辺負荷で埋め込む多項式時間アルゴリズム
- 3点上のオンラインページ移動問題に対する新しい上下界
- リングネットワークにおけるページ移動について
- 効率的に分割できるグラフの同点数格子への小さい辺負荷を持つ埋め込み
- 定数コストの横断辺を持つ梯子状ネットワークの最適化
- 二次元三角格子型無線ネットワークにおける電力最小ブロードキャスト