Incremental Approximate Maximum Flow in $m^{1/2+o(1)}$ update time

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.

Incremental Approximate Maximum Flow in $m^{1 / 2 + o (1)}$ update time

文献摘要

讨论

讲解博客

AI智能校验

Incremental Approximate Maximum Flow in $m^{1 / 2 + o (1)}$ update time

文献摘要

讨论

讲解博客

AI智能校验

Incremental Approximate Maximum Flow in m1/2+o(1)m1/2+o(1) update time

文献摘要

讨论

|讲解博客

|AI智能校验

Incremental Approximate Maximum Flow in m1/2+o(1)m1/2+o(1) update time

文献摘要

讨论

|讲解博客

|AI智能校验

Incremental Approximate Maximum Flow in $m^{1 / 2 + o (1)}$ update time

讲解博客

AI智能校验

Incremental Approximate Maximum Flow in $m^{1 / 2 + o (1)}$ update time

讲解博客

AI智能校验