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 Plus annual

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

Global: Zendy Plus monthly

Global: Zendy Tools annual

Global: Zendy Tools monthly

Global: Zendy Free Plan

Distributed network optimization algorithms, such as minimum spanning tree,minimum cut, and shortest path, are an active research area in distributedcomputing. This paper presents a fast distributed algorithm for such problemsin the CONGEST model, on networks that exclude a fixed minor.  On general graphs, many optimization problems, including the ones mentionedabove, require $\tilde\Omega(\sqrt n)$ rounds of communication in the CONGESTmodel, even if the network graph has a much smaller diameter. Naturally, thenext step in algorithm design is to design efficient algorithms which bypassthis lower bound on a restricted class of graphs. Currently, the only knownmethod of doing so uses the low-congestion shortcut framework of Ghaffari andHaeupler [SODA'16]. Building off of their work, this paper proves that excludedminor graphs admit high-quality shortcuts, leading to an $\tilde O(D^2)$ roundalgorithm for the aforementioned problems, where $D$ is the diameter of thenetwork graph. To work with excluded minor graph families, we utilize the GraphStructure Theorem of Robertson and Seymour. To the best of our knowledge, thisis the first time the Graph Structure Theorem has been used for an algorithmicresult in the distributed setting.  Even though the proof is involved, merely showing the existence of goodshortcuts is sufficient to obtain simple, efficient distributed algorithms. Inparticular, the shortcut framework can efficiently construct near-optimalshortcuts and then use them to solve the optimization problems. This, combinedwith the very general family of excluded minor graphs, which includes mostother important graph classes, makes this result of significant interest.

Minor Excluded Network Families Admit Fast Distributed Algorithms