PRACTICAL EFFICIENCY OF MAXIMUM FLOW ALGORITHMS USING MA ORDERINGS AND PREFLOWS

スポンサーリンク

概要

• 論文の詳細を見る

• Fujishige proposed a polynomial-time maximum flow algorithm using maximum adjacency (MA) orderings. Computational results by Fujishige and Isotani showed that the algorithm was slower in practice than Goldberg and Tarjan's algorithm. In this paper we propose an improved version of Fujishige's algorithm using preflows. Our computational results show that the improved version is much faster than the original one in practice.

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

著者

• Fujishige Satoru

  Kyoto University

• Matsuoka Yuji

  Tokyo University

関連論文

• 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

スポンサーリンク