论文标题
在包装低直径的跨树木上
On Packing Low-Diameter Spanning Trees
论文作者
论文摘要
图形的边缘连接性是最基本的图理论概念之一。 1961年的Tutte和Nash-Williams的著名树包装定理指出，每个$ k $ - 边缘连接的图形$ g $都包含$ \ cal {t} $ $ \ lfloor k/2 \ rfloor $ ed \ rfloor $ edge-edise-disejoint跨越树木，我们将其称为树包装；树包装的直径$ \ cal {t} $是$ \ cal {t} $中任何树的最大直径。树木包装的理想特性既足够且对于利用分布式通信中图的高连接性，这既足够且必要的，就是它的直径很低。然而，尽管在这一领域进行了广泛的研究，但仍不清楚如何计算树木包装，其直径在$ | v（g）| $中，在低直径图$ g $中，或者是如何显示这种包装不存在。 在本文中，我们在树木包装的直径上提供了第一个非平凡的上和下限。首先，我们表明，对于每一个$ k $ - edgeed $ n $ vertex Graph $ g $直径$ d $，都有一个树包装$ \ cal {t} $ size $ω（k）$，直径$ o（（（101k \ log log n）^d），这会导致大多数$ 2 $ 2 $ 2 $ 2 $ 2 $ 2 $。其次，我们表明，对于每一个$ k $ - 连接的$ n $ - vertex图$ g $ diameter $ d $，$ g [p] $的直径为$ o（k^{d（d+1）/2}）$具有很高的可能性，其中$ g [p] $可以通过$ g $ $ g $ probibality $ p $ $ $ p = n/pog p = n/k）这提供了$ω（k/\ log n）$ exge-disexixexexexexexexexexexert of直径的包装，最多只能$ o（k^{（d（d+1）/2）}）$。然后，我们证明这两个结果几乎很紧。最后，我们表明，如果图形中的每个顶点都有$ k $ edge-edise-disjoint路径，最多可连接它们的$ d $，则有一个大小$ k $的树包装，直径$ o（d \ log n）$，导致edge-congestion $ o（\ log n）$。我们还提供了分布式计算中低直径树包装的几种应用。
Edge connectivity of a graph is one of the most fundamental graph-theoretic concepts. The celebrated tree packing theorem of Tutte and Nash-Williams from 1961 states that every $k$-edge connected graph $G$ contains a collection $\cal{T}$ of $\lfloor k/2 \rfloor$ edge-disjoint spanning trees, that we refer to as a tree packing; the diameter of the tree packing $\cal{T}$ is the largest diameter of any tree in $\cal{T}$. A desirable property of a tree packing, that is both sufficient and necessary for leveraging the high connectivity of a graph in distributed communication, is that its diameter is low. Yet, despite extensive research in this area, it is still unclear how to compute a tree packing, whose diameter is sublinear in $|V(G)|$, in a low-diameter graph $G$, or alternatively how to show that such a packing does not exist. In this paper we provide first non-trivial upper and lower bounds on the diameter of tree packing. First, we show that, for every $k$-edge connected $n$-vertex graph $G$ of diameter $D$, there is a tree packing $\cal{T}$ of size $Ω(k)$, diameter $O((101k\log n)^D)$, that causes edge-congestion at most $2$. Second, we show that for every $k$-edge connected $n$-vertex graph $G$ of diameter $D$, the diameter of $G[p]$ is $O(k^{D(D+1)/2})$ with high probability, where $G[p]$ is obtained by sampling each edge of $G$ independently with probability $p=Θ(\log n/k)$. This provides a packing of $Ω(k/\log n)$ edge-disjoint trees of diameter at most $O(k^{(D(D+1)/2)})$ each. We then prove that these two results are nearly tight. Lastly, we show that if every pair of vertices in a graph has $k$ edge-disjoint paths of length at most $D$ connecting them, then there is a tree packing of size $k$, diameter $O(D\log n)$, causing edge-congestion $O(\log n)$. We also provide several applications of low-diameter tree packing in distributed computation.
