Use of dynamic trees in a network simplex algorithm for the maximum flow problem |
| |
Authors: | Andrew V Goldberg Michael D Grigoriadis Robert E Tarjan |
| |
Institution: | (1) Department of Computer Science, Stanford University, 94305 Stanford, CA, USA;(2) Department of Computer Science, Rutgers University, 08903 New Brunswick, NJ, USA;(3) Department of Computer Science, Princeton University, 08544 Princeton, NJ, USA;(4) AT&T Bell Laboratories, 07974 Murray Hill, NY, USA |
| |
Abstract: | Goldfarb and Hao (1990) have proposed a pivot rule for the primal network simplex algorithm that will solve a maximum flow problem on ann-vertex,m-arc network in at mostnm pivots and O(n
2
m) time. In this paper we describe how to extend the dynamic tree data structure of Sleator and Tarjan (1983, 1985) to reduce the running time of this algorithm to O(nm logn). This bound is less than a logarithmic factor larger than those of the fastest known algorithms for the problem. Our extension of dynamic trees is interesting in its own right and may well have additional applications.Research partially supported by a Presidential Young Investigator Award from the National Science Foundation, Grant No. CCR-8858097, an IBM Faculty Development Award, and AT&T Bell Laboratories.Research partially supported by the Office of Naval Research, Contract No. N00014-87-K-0467.Research partially supported by the National Science Foundation, Grant No. DCR-8605961, and the Office of Naval Research, Contract No. N00014-87-K-0467. |
| |
Keywords: | Algorithms complexity data structures dynamic trees graphs linear programming maximum flow network flow network optimization |
本文献已被 SpringerLink 等数据库收录! |
|