Efficient Maximum Flow Algorithms
Report ID: TR-311-91Author: Tarjan, Robert E.
Date: 1991-03-00
Pages: 11
Download Formats: |PDF|
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.