Linear-time algorithms for max flow and multiple-source shortest paths in unit-weight planar graphs
Linear-time algorithms for max flow and multiple-source shortest paths in unit-weight planar graphs
复制标题
单位权重平面图中最大流和多源最短路径的线性时间算法
DOI：
10.1145/2488608.2488702
复制
发表时间：
2013
期刊：
影响因子：
--
通讯作者：
P. Klein
中科院分区：
文献类型：
--
作者：
David Eisenstat;P. Klein
我们给出了平面图中两个问题的简单线性时间算法：单位容量有向图中的最大st流问题和单位长度无向图中的多源最短路径问题。
We give simple linear-time algorithms for two problems in planar graphs: max st-flow in directed graphs with unit capacities, and multiple-source shortest paths in undirected graphs with unit lengths.