Efficient Maximum Flow Algorithms

Abstract:

Discovering efficient algorithms to compute flows in networks has been
a goal of researchers in operations research and computer science for
over 35 years. In this paper we review some recent developments in
algorithms for the single-commodity maximum flow problem, and we
comment on possible additional improvements. Our criterion for
efficiency is theoretical worst-case running time on large sparse
problems, ignoring constant factors.