Layered Augmenting Path Algorithms
Layered Augmenting Path Algorithms
复制标题
分层增强路径算法
DOI：
10.1287/moor.11.2.362
复制
发表时间：
1986
期刊：
影响因子：
--
通讯作者：
M. Trick
中科院分区：
文献类型：
--
作者：
É. Tardos;C. Tovey;M. Trick
增强路径算法，首先由 Ford 和 Fulkerson Ford、L. R.、D. R. Fulkerson 提出。 1962.网络中的流动。新泽西州普林斯顿的普林斯顿大学出版社广泛用于优化。示例包括 Schonsleben 的多类阵交集算法 Schonsleben, P. 1980。Ganzzahlige 多类阵交集算法。博士论文，Eidgenossischen Technischen Hochschule，苏黎世。Lawler 和 Martel 的最大多拟阵网络流算法 Lawler、E. L.、C. U. Martel。 1982.计算最大多拟阵网络流。数学。歌剧。 Res.7 334--347.，Frank 的 Edmonds-Giles 多面体算法 Frank, A. 1984。寻找 Edmonds-Giles 多面体的可行向量。 J.康宾.理论系列。 B36 221-239。以及 Cunningham 测试拟阵多面体成员资格的算法 Cunningham, H. W. 1984。测试拟阵多面体的成员资格。 J.康宾.理论系列。 B36 161--188..
这里，我们通过使用类似于 Dinits 最大流算法的方法，对上述算法进行了一个数量级的改进。 Dinits, E. A. 1970。通过功率估计解决网络中最大流问题的算法。苏联数学。多克.11 1277--1280..
Augmenting path algorithms, first introduced by Ford and Fulkerson Ford, L. R., D. R. Fulkerson. 1962. Flows in Networks. Princeton University Press, Princeton, N.J., are widely used in optimization. Examples include Schonsleben's polymatroid intersection algorithm Schonsleben, P. 1980. Ganzzahlige polymatroid-intersection-algorithmen. Ph.D. thesis, Eidgenossischen Technischen Hochschule, Zurich., the maximum polymatroidal network flow algorithm of Lawler and Martel Lawler, E. L., C. U. Martel. 1982. Computing maximal polymatroidal network flows. Math. Oper. Res.7 334--347., Frank's algorithm for the Edmonds--Giles polyhedron Frank, A. 1984. Finding feasible vectors of Edmonds-Giles polyhedra. J. Combin. Theory Ser. B36 221-239. and Cunningham's algorithm for testing membership in matroid polyhedra Cunningham, H. W. 1984. Testing membership in matroid polyhedra. J. Combin. Theory Ser. B36 161--188..
Here we give an order of magnitude improvement for the above algorithms by using an approach analogous to that of Dinits' maximum flow algorithm Dinits, E. A. 1970. Algorithm for solution of a problem of maximum flow in a network with power estimation. Soviet Math. Dokl.11 1277--1280..