On Packing Low-Diameter Spanning Trees and Its Application in Distributed Computing (Zihan Tan)

Abstract

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 of k/2 edge-disjoint spanning trees, that we refer to as a tree packing; the diameter of the tree packing is the largest diameter of any tree in the tree packing. A desirable property of a tree packing, that is both sufficient and necessary for leveraging the high connectivity of a graph in distributed communication networks, 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, together with several applications of low-diameter tree packing in the settings of distributed network optimization.

This talk is based on joint work with Julia Chuzhoy and Merav Partera.

Time

Speaker

Room