A faster deterministic maximum flow algorithm
A faster deterministic maximum flow algorithm
复制标题
更快的确定性最大流量算法
DOI：
--
复制
发表时间：
1992
期刊：
影响因子：
--
通讯作者：
R. Tarjan
中科院分区：
文献类型：
--
作者：
Valerie King;S. Rao;R. Tarjan
我们描述了1990年Cheriyan， Hagerup和Mehlhorn随机化算法的确定性版本，用于计算有向图上的最大流量，该有向图具有<斜体>n</斜体>节点和<斜体>m</斜体>边，运行时间<斜体>O</斜体>（<斜体>mn</斜体> + <斜体>n</斜体><斜体>2+ε</斜体>，对于任何常数<斜体>ε</斜体>）。这改进了Alon在1989年提出的<斜体> 0 </斜体>（<斜体>mn</斜体> + <斜体>n</斜体><斜体>8/3</斜体>log <斜体>n</斜体>）的界[A]，并给出了<斜体>m</斜体> >mn</斜体>n</斜体><斜体>1+ε</斜体>的确定性算法。因此，它扩展了<italic>m/n</italic>的范围，其中<italic>O</italic>(<italic>mn</italic>)算法已知，并匹配了Goldberg和Tarjan [GT]的1988算法，用于<italic>m/n</italic>的较小值。
We describe a deterministic version of a 1990 Cheriyan, Hagerup, and Mehlhorn randomized algorithm for computing the maximum flow on a directed graph with <italic>n</italic> nodes and <italic>m</italic> edges which runs in time <italic>O</italic>(<italic>mn</italic> + <italic>n</italic><supscrpt>2+ε</supscrpt>, for any constant <italic>ε</italic>. This improves upon Alon's 1989 bound of <italic>O</italic>(<italic>mn</italic> + <italic>n</italic><supscrpt>8/3</supscrpt>log <italic>n</italic>) [A] and gives an <italic>O</italic>(<italic>mn</italic>) deterministic algorithm for all <italic>m</italic> > <italic>n</italic><supscrpt>1+ε</supscrpt>. Thus it extends the range of <italic>m/n</italic> for which an <italic>O</italic>(<italic>mn</italic>) algorithm is known, and matches the 1988 algorithm of Goldberg and Tarjan [GT] for smaller values of <italic>m/n</italic>.