独立流れ問題を解く算法

DOI Web Site 被引用文献3件

書誌事項

タイトル別名
  • ALGORITHMS FOR SOLVING THE INDEPENDENT-FLOW PROBLEMS

抄録

G(V、A^*;V_1、V_2)を、点集合V、枝集合A^*、および、"入口"V_1(⊆V)、"出口"V_2(⊆7)をもつグラフとする。簡単のためV_1∩V_2:φとしておく。グラフGの各枝αには、その容量c(α)と単位流量当りの費用γ(a)とが付与されているとする。さらに、人ロV_1と出口V_2上に、それぞれ、ホリマトロイドP_1(V_1、ρ_1)、P_2(V_2、ρ_2)が定義されているとする。以上の諸量の定義されたグラフをネットワークNと呼ぶことにする。N上の"独立流れ"とは、各枝の容量条件を満たす入口V_1から出口V_2へのG上の流れであり、かつ、V_1への流入ベクトルがP_1の、V_2からの流出ベクトルがP_2の、それぞれ、独立ベクトルであるようなものである。ただし、V_1への流入ベクトルとは、各v^εV_1にvへの流入量を対応づけるベクトルである(流出ベクトルについても同様)。"独立流れ問題"とは、(1)N上の最大独立流れ(すなわち、V_1からV_2への最大流量をもつN上の独立流れ)を見出す問題、および、(2)N上の最大独立流れのうちで費用が最小であるものを見出す問題、のことである。本論文では、与えられた独立流れに関連して定義される補助ネットワークを用いて独立流れ問題を解く算法を提示する。プライマル・デュアルな形の算法は概略つぎのようである。N上のある独立流れから出発して、補助ネットワーク上の最短路を見出し、それに基づいて流れを変更し、流量が増加した新たな独立流れ(問題(2)の場合は同じ流量をもつ独立流れのうちで最小費用の独立流れ)を得る。さらに、得られた独立流れに関連する補助ネットワ-クを構成し、以上の手続きを繰返す。問題(2)に対しては、プライマルな形の算法も提示してある。これらの算法を導出する過程において、最大独立流れや最小費用の最大独立流れを特徴づけるいくつかの命題が、構成的に証明される。複数個の(ポリ)マトロイドが関係するような、今までに提起されている問題のうちの多くは、独立流れ問題として"自然な形で定式化される。ネットワーク流れ問題としての定式化が多くの組合せ的問題に対して有効であったのと同様に、独立流れ問題としての定式化が(ポリ)マトロイド的な組合せ的問題に対して有効である。なお、パラメタc(a)(a^εA*)、ρi(A)(A⊆V i;i=1、2)が可約な場合、本論文で提示した算法は有限回の操作の後に終了し解を与える。一般の独立流れ問題に対し本論文で提示した算法が有限回の操作の後に終了するか否かの問題、有限回で終了するとすればその手間の評価の問題、などは今後に残された課題である。

収録刊行物

被引用文献 (3)*注記

もっと見る

キーワード

詳細情報 詳細情報について

問題の指摘

ページトップへ