solidot新版网站常见问题,请点击这里查看。
消息
本文已被查看470次
Cut Tree Structures with Applications on Contraction-Based Sparsification. (arXiv:1707.00572v1 [math.CO])
来源于:arXiv
We introduce three new cut tree structures of graphs $G$ in which the vertex
set of the tree is a partition of $V(G)$ and contractions of tree vertices
satisfy sparsification requirements that preserve various types of cuts.
Recently, Kawarabayashi and Thorup \cite{Kawarabayashi2015a} presented the
first deterministic near-linear edge-connectivity recognition algorithm. A
crucial step in this algorithm uses the existence of vertex subsets of a simple
graph $G$ whose contractions leave a graph with $\tilde{O}(n/\delta)$ vertices
and $\tilde{O}(n)$ edges ($n := |V(G)|$) such that all non-trivial min-cuts of
$G$ are preserved. We improve this result by eliminating the poly-logarithmic
factors, that is, we show a contraction-based sparsification that leaves
$O(n/\delta)$ vertices and $O(n)$ edges and preserves all non-trivial min-cuts.
We complement this result by giving a sparsification that leaves $O(n/\delta)$
vertices and $O(n)$ edges such that all (possibly not minimum) cuts of size
l 查看全文>>