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

Global: Zendy Free Plan

Global: Zendy Tools monthly

Global: Zendy Plus monthly

Consider the following 2-respecting min-cut problem. Given a weighted graph$G$ and its spanning tree $T$, find the minimum cut among the cuts that containat most two edges in $T$. This problem is an important subroutine in Karger'scelebrated randomized near-linear-time min-cut algorithm [STOC'96]. We presenta new approach for this problem which can be easily implemented in manysettings, leading to the following randomized min-cut algorithms for weightedgraphs.  * An $O(m\frac{\log^2 n}{\log\log n} + n\log^6 n)$-time sequential algorithm:This improves Karger's $O(m \log^3 n)$ and $O(m\frac{(\log^2 n)\log(n^2/m)}{\log\log n} + n\log^6 n)$ bounds when the input graph is not extremelysparse or dense. Improvements over Karger's bounds were previously known onlyunder a rather strong assumption that the input graph is simple [Henzinger etal. SODA'17; Ghaffari et al. SODA'20]. For unweighted graphs with paralleledges, our bound can be improved to $O(m\frac{\log^{1.5} n}{\log\log n} +n\log^6 n)$.  * An algorithm requiring $\tilde O(n)$ cut queries to compute the min-cut ofa weighted graph: This answers an open problem by Rubinstein et al. ITCS'18,who obtained a similar bound for simple graphs.  * A streaming algorithm that requires $\tilde O(n)$ space and $O(\log n)$passes to compute the min-cut: The only previous non-trivial exact min-cutalgorithm in this setting is the 2-pass $\tilde O(n)$-space algorithm on simplegraphs [Rubinstein et al., ITCS'18] (observed by Assadi et al. STOC'19).  In contrast to Karger's 2-respecting min-cut algorithm which deployssophisticated dynamic programming techniques, our approach exploits some cutestructural properties so that it only needs to compute the values of $\tildeO(n)$ cuts corresponding to removing $\tilde O(n)$ pairs of tree edges, anoperation that can be done quickly in many settings.

Weighted Min-Cut: Sequential, Cut-Query and Streaming Algorithms