TWO EFFICIENT ALGORITHMS FOR THE GENERALIZED MAXIMUM BALANCED FLOW PROBLEM

スポンサーリンク

概要

• 論文の詳細を見る

• Minoux considered the maximum balanced flow problem, i.e. the problem of finding a maximum flow in a two-terminal network N=(V, A) with source s and sink t satisfying the constraint that any arc-flow of N is bounded by a fixed proportion of the total flow value from s to t, where V is vertex set and A is arc set. Several efficient algorithms, so far, have been proposed for this problem. As a natural generalization of this problem we focus on the problem of maximizing the total flow value of a generalized flow in a network N=(V, A) with gains γ(a)>0 (a∈A) satisfying any arc-flow of N is bounded by a fixed proportion of the total flow value from s to t, where γ(a)f(a) units arrive at the vertex w for each arc-flow f(a) (a≡(v, w)∈A) entering vertex v in a generalized flow in AF. We call it the generalized maximum balanced flow problem and if γ(a)=1 for any a∈A then it is a maximum balanced flow problem. The authors believe that no algorithms have been shown for this generalized version. Our main results are to propose two polynomial algorithms for solving the generalized maximum balanced flow problem. The first algorithm runs in O(mM(n, m, B')log B) time, where B is the maximum absolute value among integral values used by an instance of the problem, and M(n, m, B') denotes the complexity of solving a generalized maximum flow problem in a network with n vertices, and m arcs, and a rational instance expressed with integers between 1 and B'. In the second algorithm we combine a parameterized technique of Megiddo with one of algorithms for the generalized maximum flow problem, and show that it runs in O({M(n, m, B')}^2)time.

• 社団法人日本オペレーションズ・リサーチ学会の論文

著者

• Su Chien

  Tokuritsu Co. Ltd.

• Nakayama Akira

  Fukushima University

関連論文

• TWO EFFICIENT ALGORITHMS FOR THE GENERALIZED MAXIMUM BALANCED FLOW PROBLEM
• 1-B-8 Dijkstra-based scaling algorithm for the single-source shortest-paths problem with edges of integral negative length
• 1-F-2 An extended Edmonds-Karp algorithm for a flow problem with gains and losses and its application
• DIJKSTRA-BASED ALGORITHMS FOR THE SHORTEST PATH PROBLEM WITH EDGES OF NEGATIVE LENGTH

スポンサーリンク