An Algorithm For The Maximum Balanced Flow Problem

スポンサーリンク

概要

• 論文の詳細を見る

• We consider the maximum balanced flow problem, which is a maximum flow problem with an additional constraint described in terms of a balancing rate function. In the present paper, we propose an algorithm for the maximum balanced flow problem by employing the binary search and a parametric method. Our algorithm requires O ((?ogM2M) T(n, m)) time, where T(n, m) is the time for the maximum flow computation for a two terminal network with n vertices and m arcs, and M is the maximum flow value of the maximum flow problem without the additional constraint (i.e., usual maximum flow problem), and ?ogMis the maximum integer less than or equal to logM.

• 小樽商科大学の論文

著者

• 中山 明

  小樽商科大学

• Nakayama A

  Otaru Univ. Jpn

関連論文

• Another Easy Proof of NP-Completeness on the Maximum Integral Vertex-Balanced Flow Problem
• An Algorithm For The Maximum Balanced Flow Problem
• 最小費用流問題に対する多項式時間の双対単体法
• 平衡係数関数が一定となる場合の最大平衡フロー問題に対する多項式時間アルゴリズム

スポンサーリンク