ﻻ يوجد ملخص باللغة العربية
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 terminals exist. As a step towards this goal, we study a thresholded version of the problem: for a given parameter $c$, find a smaller graph, which we call connectivity-$c$ mimicking network, which preserves connectivity among $k$ terminals exactly up to the value of $c$. We show that connectivity-$c$ mimicking networks with $O(kc^4)$ edges exist and can be found in time $m(clog n)^{O(c)}$. We also give a separate algorithm that constructs such graphs with $k cdot O(c)^{2c}$ edges in time $mc^{O(c)}log^{O(1)}n$. These results lead to the first data structures for answering fully dynamic offline $c$-edge-connectivity queries for $c ge 4$ in polylogarithmic time per query, as well as more efficient algorithms for survivable network design on bounded treewidth graphs.
A recent palette sparsification theorem of Assadi, Chen, and Khanna [SODA19] states that in every $n$-vertex graph $G$ with maximum degree $Delta$, sampling $O(log{n})$ colors per each vertex independently from $Delta+1$ colors almost certainly allow
We show a deterministic algorithm for computing edge connectivity of a simple graph with $m$ edges in $m^{1+o(1)}$ time. Although the fastest deterministic algorithm by Henzinger, Rao, and Wang [SODA17] has a faster running time of $O(mlog^{2}mloglog
The vertex connectivity of an $m$-edge $n$-vertex undirected graph is the smallest number of vertices whose removal disconnects the graph, or leaves only a singleton vertex. In this paper, we give a reduction from the vertex connectivity problem to a
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-
The problem of sparsifying a graph or a hypergraph while approximately preserving its cut structure has been extensively studied and has many applications. In a seminal work, Benczur and Karger (1996) showed that given any $n$-vertex undirected weigh