A 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.

著者

• Fujishige Satoru

  Kyoto University

• Takabatake Takashi

  Kochi Gakuen College

• Eguchi Akinobu

  Panasonic Mobile Communications Co. Ltd.

関連論文

• A TREE PARTITIONING PROBLEM ARISING FROM AN EVACUATION PROBLEM IN TREE DYNAMIC NETWORKS
• PRACTICAL EFFICIENCY OF MAXIMUM FLOW ALGORITHMS USING MA ORDERINGS AND PREFLOWS
• NEW MAXIMUM FLOW ALGORITHMS BY MA ORDERMGS AND SCALING
• A POLYNOMIAL-TIME ALGORITHM FOR THE GENERALIZED INDEPENDENT-FLOW PROBLEM

スポンサーリンク