ISSN:
1436-4646
Keywords:
Algorithms
;
complexity
;
data structures
;
dynamic trees
;
graphs
;
linear programming
;
maximum flow
;
network flow
;
network optimization
Source:
Springer Online Journal Archives 1860-2000
Topics:
Computer Science
,
Mathematics
Notes:
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.
Type of Medium:
Electronic Resource
URL:
http://dx.doi.org/10.1007/BF01594940
Permalink
