平衡係数関数が一定となる場合の最大平衡フロー問題に対する多項式時間アルゴリズム

スポンサーリンク

概要

• 論文の詳細を見る

• M。Minouxは、最大平衡フロー問題を考際した。この問題は、最大フロー問題の一種、つまり、最大フロー問題に、さらに、ある与えられた関数(平衡係数関数と呼ばれる。)によって定められる制約条件が加わったものである。この論文では、最大平衡フロー問題に対して、実際的に高速かつ、簡明なアルゴリズムを提案する。しかも、平衡係数関数が一定となる場合に提案されたアルゴリズムはO(mT(n、m))の手間がかかることを示す。ただし、T(n、m)は、n個の点とm本の枝をもつネットワークに対して最大フロー問題を解くのに必要な計算時間とする。

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

著者

• 中山 明

  小樽商科大学

• 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
• 最小費用流問題に対する多項式時間の双対単体法
• 平衡係数関数が一定となる場合の最大平衡フロー問題に対する多項式時間アルゴリズム

スポンサーリンク