An O (n log n) algorithm for maximum st-flow in a directed planar graph
An O (n log n) algorithm for maximum st-flow in a directed planar graph
复制标题
有向平面图中最大 st 流的 O (n log n) 算法
DOI：
--
复制
发表时间：
2006
期刊：
影响因子：
--
通讯作者：
P. Klein
中科院分区：
文献类型：
--
作者：
G. Borradaile;P. Klein
我们给出了在有向平面图中寻找最大<i>st</i>-流的第一个正确<i>的O</i>（nlog<i>n</i><i></i>经过一个预处理步骤，包括在寻找单源最短路径距离的双重，该算法包括反复饱和的最左边的残留的<i>s</i>到<i>t</i>路径。
We give the first correct <i>O</i>(<i>n</i> log <i>n</i>) algorithm for finding a maximum <i>st</i>-flow in a directed planar graph. After a preprocessing step that consists in finding single-source shortest-path distances in the dual, the algorithm consists of repeatedly saturating the leftmost residual <i>s</i>-to-<i>t</i> path.