凸関数コストをもつ流れ網におけるフロウの性質

翁長 健治  角所 収  加藤 金正  

誌名
電子情報通信学会論文誌 A   Vol.J52-A   No.2   pp.47-54
発行日: 1969/02/25
Online ISSN: 
DOI: 
Print ISSN: 0373-6091
論文種別: 論文・資料
専門分野: 
キーワード: 


本文: PDF(658.8KB)>>
論文を購入




あらまし: 
流れ網においてフロウの伝送にコストのかかる場合最小コストをもつ単一フロウは重要で多くの研究がある.固定分のない線形コストの場合については最小コスト道法とよばれるアルゴリズムが開発されている.本論文は各枝がΦ(0)=0(無固定分)をみたし流量λの凸関数であるコストΦλ)をもつ一般の流れ網におけるフロウFのふるまいをグラフ論的手法で解析し,どのフロウ閉路Kのコスト増分φKF)も非負でなければならないという最小コストのための必要十分条件を求めた.この条件にもとずき与えられた総流量をもつ最小コストフロウの構成のアルゴリズムを示した.