English (United Kingdom)

https://curated-unify.zendy.io/wp-json/zendy-region/v1/featured_content/oa?rat=en

https://curated-unify.zendy.io/wp-json/zendy-region/v1/highlighted_journal/

Global: Zendy Tools annual

Presents the keyphrase highlighting as premium feature

Keyphrase Highlighting

Presents the summarisation as premium feature

Summarisation

Insights

Presents the pdf analysis as premium feature

PDF Analysis

Presents the zaia usage as premium feature

ZAIA

Global: Zendy Tools monthly

Global: Zendy Plus monthly

Presents the access of premium content as premium feature

Premium Content

Global: Zendy Plus annual

Global: Zendy Free Plan

We study the problem of finding flows in undirected graphs so as to minimizethe weighted $p$-norm of the flow for any $p > 1$. When $p=2$, the problem isthat of finding an electrical flow, and its dual is equivalent to solving aLaplacian linear system. The case $p = \infty$ corresponds to finding amin-congestion flow, which is equivalent to max-flows. A typical algorithmicconstruction for such problems considers vertex potentials corresponding to theflow conservation constraints, and has two simple types of update steps: cycletoggling, which modifies the flow along a cycle, and cut toggling, whichmodifies all potentials on one side of a cut. Both types of steps are typicallyperformed relative to a spanning tree $T$; then the cycle is a fundamentalcycle of $T$, and the cut is a fundamental cut of $T$. In this paper, we showthat these simple steps can be used to give a novel efficient implementationfor the $p = 2$ case and to find near-optimal $p$-norm flows in a low number ofiterations for all values of $p > 1$. Compared to known faster algorithms forthese problems, our algorithms are simpler, more combinatorial, and also exposeseveral underlying connections between these algorithms and dynamic graph datastructures that have not been formalized previously.

Cut-Toggling and Cycle-Toggling for Electrical Flow and Other p-Norm Flows