Construction and Analysis of Network Flow Problem Which Forces Karzanov Algorithm 0(n^3) Running Time
Author(s)
Baratz, Alan E.![Thumbnail](/bitstream/handle/1721.1/148911/MIT-LCS-TM-083.pdf.jpg?sequence=3&isAllowed=y)
DownloadMIT-LCS-TM-083.pdf (2.903Mb)
Metadata
Show full item recordAbstract
The intest of this paper is to demonstrate the construction of a network flow problem which will force the Karzanov "Preflow" algorithm to run in its theoretic worst case time 0(n^3). Once such a "bad case" network has been constructed, an analysis is performed to determine the exact time required by the algorithm to computer the maximum flow through the network.
Date issued
1977-05Series/Report no.
MIT-LCS-TM-083