ﻻ يوجد ملخص باللغة العربية
We provide a simple new randomized contraction approach to the global minimum cut problem for simple undirected graphs. The contractions exploit 2-out edge sampling from each vertex rather than the standard uniform edge sampling. We demonstrate the power of our new approach by obtaining better algorithms for sequential, distributed, and parallel models of computation. Our end results include the following randomized algorithms for computing edge connectivity with high probability: -- Two sequential algorithms with complexities $O(m log n)$ and $O(m+n log^3 n)$. These improve on a long line of developments including a celebrated $O(m log^3 n)$ algorithm of Karger [STOC96] and the state of the art $O(m log^2 n (loglog n)^2)$ algorithm of Henzinger et al. [SODA17]. Moreover, our $O(m+n log^3 n)$ algorithm is optimal whenever $m = Omega(n log^3 n)$. Within our new time bounds, whp, we can also construct the cactus representation of all minimal cuts. -- An $~O(n^{0.8} D^{0.2} + n^{0.9})$ round distributed algorithm, where D denotes the graph diameter. This improves substantially on a recent breakthrough of Daga et al. [STOC19], which achieved a round complexity of $~O(n^{1-1/353}D^{1/353} + n^{1-1/706})$, hence providing the first sublinear distributed algorithm for exactly computing the edge connectivity. -- The first $O(1)$ round algorithm for the massively parallel computation setting with linear memory per machine.
We study several problems related to graph modification problems under connectivity constraints from the perspective of parameterized complexity: {sc (Weighted) Biconnectivity Deletion}, where we are tasked with deleting~$k$ edges while preserving bi
The tree augmentation problem (TAP) is a fundamental network design problem, in which the input is a graph $G$ and a spanning tree $T$ for it, and the goal is to augment $T$ with a minimum set of edges $Aug$ from $G$, such that $T cup Aug$ is 2-edge-
We design an algorithm for computing connectivity in hypergraphs which runs in time $hat O_r(p + min{lambda^{frac{r-3}{r-1}} n^2, n^r/lambda^{r/(r-1)}})$ (the $hat O_r(cdot)$ hides the terms subpolynomial in the main parameter and terms that depend o
Graph compression or sparsification is a basic information-theoretic and computational question. A major open problem in this research area is whether $(1+epsilon)$-approximate cut-preserving vertex sparsifiers with size close to the number of termin
We consider the problem of finding textit{semi-matching} in bipartite graphs which is also extensively studied under various names in the scheduling literature. We give faster algorithms for both weighted and unweighted case. For the weighted case,