solidot新版网站常见问题,请点击这里查看。
消息
本文已被查看4878次
Contraction-Based Sparsification in Near-Linear Time. (arXiv:1810.03865v1 [math.CO])
来源于:arXiv
Recently, Kawarabayashi and Thorup presented the first deterministic
edge-connectivity recognition algorithm in near-linear time. A crucial step in
their algorithm uses the existence of vertex subsets of a simple graph $G$ on
$n$ vertices whose contractions leave a multigraph with $\tilde{O}(n/\delta)$
vertices and $\tilde{O}(n)$ edges that preserves all non-trivial min-cuts of
$G$.
We show a very simple argument that improves this contraction-based
sparsifier by eliminating the poly-logarithmic factors, that is, we show a
contraction-based sparsification that leaves $O(n/\delta)$ vertices and $O(n)$
edges, preserves all non-trivial min-cuts and can be computed in near-linear
time $\tilde{O}(|E(G)|)$. As consequence, every simple graph has
$O((n/\delta)^2)$ non-trivial min-cuts.
Our approach allows to represent all non-trivial min-cuts of a graph by a
cactus representation, whose cactus graph has $O(n/\delta)$ vertices. Moreover,
this cactus representation can be derived directly from 查看全文>>