Premium
A comparison of phase and nonphase network flow algorithms
Author(s) -
Martel Charles
Publication year - 1989
Publication title -
networks
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 0.977
H-Index - 64
eISSN - 1097-0037
pISSN - 0028-3045
DOI - 10.1002/net.3230190607
Subject(s) - parameterized complexity , algorithm , computer science , flow network , computation , minimum cost flow problem , flow (mathematics) , mathematics , mathematical optimization , geometry
We compare the performance of network flow algorithms based on Dinic's layered graph approach to the new Goldberg‐Tarjan (GT) algorithm. We show that for networks with small capacities, in particular for unit networks, the Dinic‐like algorithms are asymptotically faster than the GT algorithm. A second setting that we study is parameterized flow computations. Gallo, Grigoriadis, and Tarjan have shown that the GT algorithm solves this type of problem very efficiently. We show that traditional implementations of the Dinic‐like algorithms are much less efficient for solving parameterized flow problems. We also give a new implementation of a Dinic‐like algorithm that is competitive with the GT algorithm on parameterized flow networks.