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

We study a natural problem in graph sparsification, the Spanning TreeCongestion (\STC) problem. Informally, the \STC problem seeks a spanning treewith no tree-edge \emph{routing} too many of the original edges. The root ofthis problem dates back to at least 30 years ago, motivated by applications innetwork design, parallel computing and circuit design. Variants of the problemhave also seen algorithmic applications as a preprocessing step of severalimportant graph algorithms.  For any general connected graph with $n$ vertices and $m$ edges, we show thatits STC is at most $\mathcal{O}(\sqrt{mn})$, which is asymptotically optimalsince we also demonstrate graphs with STC at least $\Omega(\sqrt{mn})$. Wepresent a polynomial-time algorithm which computes a spanning tree withcongestion $\mathcal{O}(\sqrt{mn}\cdot \log n)$. We also present anotheralgorithm for computing a spanning tree with congestion$\mathcal{O}(\sqrt{mn})$; this algorithm runs in sub-exponential time when $m =\omega(n \log^2 n)$.  For achieving the above results, an important intermediate theorem is\emph{generalized Gy\H{o}ri-Lov\'{a}sz theorem}, for which Chen et al. gave anon-constructive proof. We give the first elementary and constructive proof byproviding a local search algorithm with running time $\mathcal{O}^*\left( 4^n\right)$, which is a key ingredient of the above-mentioned sub-exponential timealgorithm. We discuss a few consequences of the theorem concerning graphpartitioning, which might be of independent interest.  We also show that for any graph which satisfies certain \emph{expandingproperties}, its STC is at most $\mathcal{O}(n)$, and a corresponding spanningtree can be computed in polynomial time. We then use this to show that a randomgraph has STC $\Theta(n)$ with high probability.

Spanning Tree Congestion and Computation of Generalized Gy\H{o}ri-Lov\'{a}sz Partition