Use of dynamic trees in a network simplex algorithm for the maximum flow problem
Use of dynamic trees in a network simplex algorithm for the maximum flow problem
复制标题
在网络单纯形算法中使用动态树解决最大流问题
DOI：
10.1007/bf01594940
复制
发表时间：
1991
影响因子：
2.7
通讯作者：
R. Tarjan
中科院分区：
文献类型：
--
作者：
A. Goldberg;M. Grigoriadis;R. Tarjan
Goldfarb和Hao（1990）提出了一个主元规则，用于求解n-顶点m-弧网络上的最大流问题，该算法最多需要m个主元，时间复杂度为O（n2 m）。本文描述了如何扩展Sleator和Tarjan（1983，1985）的动态树数据结构，使该算法的运行时间减少到O（nmlogn）。这个界限是小于一个对数因子大于那些已知的最快的算法的问题。我们对动态树的扩展本身就很有趣，而且很可能有其他的应用。
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(n2m) 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.