一般化最小費用独立フロー問題とその多項式時間アルゴリズム
スポンサーリンク
概要
- 論文の詳細を見る
独立フロー問題は,複数個の入口と出口からなる点集合上に劣モジュラ制約を与えることにより,通常のネットワークフロー問題を拡張したもので,独立マッチング問題,独立割当問題など実際問題への応用範囲が広い.ここでは,各枝αについてのフローの利得α(α)を考えることにより,最小費用独立フロー問題をさらに一般化して考える.この利得のために,枝αにその始点から流れ始めたフローはα(α)倍されてその終点に到達する.本文では,このように定義される一般化最小費用独立フロー問題に対する多項式時間アルゴリズムを与える.
- 社団法人電子情報通信学会の論文
- 2002-07-29
著者
-
藤重 悟
大阪大学大学院基礎工学研究科システム人間系専攻システム科学分野
-
高畑 貴志
大阪大学
-
江口 明伸
大阪大学
-
高畑 貴志
大阪大学大学院基礎工学研究科システム科学分野
-
江口 明伸
大阪大学大学院基礎工学研究科システム人間系専攻
関連論文
- 無向ネットワークにおける流量要求を満たす施設配置問題
- 正則2部グラフに対する単純なマッチングアルゴリズム
- Gale-Shapleyの安定マッチングアルゴリズムのM〓凹関数対への拡張(最適化(1))
- 一般化最小費用独立フロー問題とその多項式時間アルゴリズム(グラフ・ネットワーク(1))
- 複基多面体:台の大きさが2以下の辺ベクトルを有する多面体の構造
- 木構造の動的ネットワークにおける施設配置問題
- 一般化最小費用独立フロー問題とその多項式時間アルゴリズム
- 劣モジュラ関数最小化の組み合せ的強多項式時間アルゴリズム : 20年近くの未解決問題を解決