A POLYNOMIAL-TIME ALGORITHM FOR THE GENERALIZED INDEPENDENT-FLOW PROBLEM
-
- Eguchi Akinobu
- Panasonic Mobile Communications Co., Ltd.
-
- Fujishige Satoru
- Kyoto University
-
- Takabatake Takashi
- Kochi Gakuen College
書誌事項
- タイトル別名
-
- Polynomial Time Algorithm for the Generalized Independent Flow Problem
この論文をさがす
説明
We consider a compound problem of the generalized minimum-cost flow problem and the independent-flow problem, which we call the generalized independent-flow problem. The generalized minimum-cost flow problem is to find a minimum-cost flow in a capacitated network with gains, where each arc flow is multiplied by a gain factor when going through an arc. On the other hand, the independent-flow problem due to Fujishige is to find a minimum-cost flow in a multiple-source multiple-sink capacitated network with submodular constraints on the set of supply vectors on the source vertex set and on the set of demand vectors on the sink vertex set. We present a polynomial-time algorithm for the generalized independent-flow problem, based on Wayne's algorithm for generalized minimum-cost flows and Fujishige's algorithm for independent flows, which can be regarded as an extension of Wallacher and Zimmermann's submodular flow algorithm.
収録刊行物
-
- 日本オペレーションズ・リサーチ学会論文誌
-
日本オペレーションズ・リサーチ学会論文誌 47 (1), 1-17, 2004
公益社団法人 日本オペレーションズ・リサーチ学会
- Tweet
詳細情報 詳細情報について
-
- CRID
- 1390282679087332480
-
- NII論文ID
- 110001183588
-
- NII書誌ID
- AA00703935
-
- ISSN
- 21888299
- 04534514
-
- NDL書誌ID
- 6888695
-
- 本文言語コード
- en
-
- データソース種別
-
- JaLC
- NDL
- Crossref
- CiNii Articles
-
- 抄録ライセンスフラグ
- 使用不可