The MA-ordering max-flow algorithm is not strongly polynomial for directed networks

The MA-ordering max-flow algorithm is not strongly polynomial for directed networks

0.00 Avg rating0 Votes
Article ID: iaor20043284
Country: Netherlands
Volume: 32
Issue: 1
Start Page Number: 31
End Page Number: 35
Publication Date: Jan 2004
Journal: Operations Research Letters
Authors:
Abstract:

Quite recently Fujishige developed a weakly polynomial-time algorithm for the maximum flow problem by applying the maximum adjacency ordering technique to directed networks. In this note, we show that the algorithm is not strongly polynomial by giving a real-valued instance for which the algorithm does not terminate.

Reviews

Required fields are marked *. Your email address will not be published.