论文标题
$ m^{1/2+o（1）} $更新时间的增量最大流量
Incremental Approximate Maximum Flow in $m^{1/2+o(1)}$ update time
论文作者
论文摘要
我们显示了$（1+ε）$ - 近似算法，用于在$ m^{1/2+O（1）} $ m $ edge插入下保持最大$ s $ - $ t $ FLOW，以定向，未加权的图形。这构成了具有良好近似保证的一般稀疏图中的第一个sublinear动态最大流量算法。
We show an $(1+ε)$-approximation algorithm for maintaining maximum $s$-$t$ flow under $m$ edge insertions in $m^{1/2+o(1)} ε^{-1/2}$ amortized update time for directed, unweighted graphs. This constitutes the first sublinear dynamic maximum flow algorithm in general sparse graphs with arbitrarily good approximation guarantee.
