NEW MAXIMUM FLOW ALGORITHMS BY MA ORDERMGS AND SCALING

スポンサーリンク

概要

• 論文の詳細を見る

• Maximum adjacency (MA) ordering has effectively been applied to graph connectivity problems by Nagamochi and Ibaraki. We show an application of MA ordering to the maximum flow problem to get a new polynomial-time algorithm and propose its scaling versions that run in O (mnlogt7) time, where TO is the number of arcs, n the number of vertices, and U the maximum capacity. We give computational results, comparing our algorithms with those of Goldberg-Tarjan and Dinitz, to show behaviors of our proposed algorithms.

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

著者

• Fujishige Satoru

  Kyoto University

• Isotani Shigueo

  Kyoto 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

スポンサーリンク