2019-09-10 | Zihan Tan:On Packing Low-Diameter Spanning Trees and Its Application in Distributed Computing



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 Parter.






Zihan Tan is a graduate student in the Computer Science Department of the University of Chicago, advised by Professor László Babai, and co-advised by Professor Julia Chuzhoy at Toyota Technological Institute at Chicago. His research interests span the areas of algorithms, combinatorial optimization and computational complexity. He is currently working on graph-theoretic problems, especially on exploring the relationship between structural notions of general graphs and designing approximation algorithms for graph routing problems. Zihan holds Bachelor’s degrees in Computer Science and in Mathematics from Tsinghua University. Prior to starting his graduate studies, he worked as a research intern at Microsoft Research Asia under the supervision of Wei Chen, and as a research assistant student at the Chinese University of Hong Kong under the supervision of Shengyu Zhang.