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/

Zendy Plus

Presents the access of premium content as premium feature

Premium Content

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

Zendy Tools

Zendy Open

Expander graphs play a central role in graph theory and algorithms. With anumber of powerful algorithmic tools developed around them, such as theCut-Matching game, expander pruning, expander decomposition, and algorithms fordecremental All-Pairs Shortest Paths (APSP) in expanders, to name just a few,the use of expanders in the design of graph algorithms has become ubiquitous.Specific applications of interest to us are fast deterministic algorithms forcut problems in static graphs, and algorithms for dynamic distance-based graphproblems, such as APSP.  Unfortunately, the use of expanders in these settings incurs a number ofdrawbacks. For example, the best currently known algorithm for decremental APSPin constant-degree expanders can only achieve a $(\logn)^{O(1/\epsilon^2)}$-approximation with $n^{1+O(\epsilon)}$ total update timefor any $\epsilon$. All currently known algorithms for the Cut Player in theCut-Matching game are either randomized, or provide rather weak guarantees.This, in turn, leads to somewhat weak algorithmic guarantees for severalcentral cut problems: for example, the best current almost linear timedeterministic algorithm for Sparsest Cut can only achieve approximation factor$(\log n)^{\omega(1)}$. Lastly, when relying on expanders in distance-basedproblems, such as dynamic APSP, via current methods, it seems inevitable thatone has to settle for approximation factors that are at least $\Omega(\log n)$.  In this paper we propose the use of well-connected graphs, and introduce anew algorithmic toolkit for such graphs that, in a sense, mirrors the abovementioned algorithmic tools for expanders. One of these new tools is theDistanced Matching game, an analogue of the Cut-Matching game forwell-connected graphs. We demonstrate the power of these new tools by obtainingbetter results for several of the problems mentioned above.

A Distanced Matching Game, Decremental APSP in Expanders, and Faster Deterministic Algorithms for Graph Cut Problems