Abstract

Edge connectivity of a graph isone of the most fundamental graph-theoretic concepts. The celebrated treepacking theorem of Tutte and Nash-Williams from 1961 states that every k-edgeconnected 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 thelargest diameter of any tree in the tree packing. A desirable property of atree packing, that is both sufficient and necessary for leveraging the highconnectivity of a graph in distributed communication networks, is that itsdiameter is low. Yet, despite extensive research in this area, it is stillunclear 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 packingdoes not exist. In this paper, we provide first non-trivial upper and lowerbounds on the diameter of tree packing, together with several applications oflow-diameter tree packing in the settings of distributed network optimization.

This talk is based onjoint work with Julia Chuzhoy and Merav Parter.

Time

9月10日（星期二）14:00—15:00

Speaker

Zihan Tan is a graduate student in theComputer Science Department of the University of Chicago, advised by ProfessorLászló Babai, and co-advised by Professor Julia Chuzhoy at Toyota TechnologicalInstitute at Chicago. His research interests span the areas of algorithms,combinatorial optimization and computational complexity. He is currentlyworking on graph-theoretic problems, especially on exploring the relationshipbetween structural notions of general graphs and designing approximationalgorithms for graph routing problems. Zihan holds Bachelor’s degrees inComputer Science and in Mathematics from Tsinghua University. Prior to startinghis graduate studies, he worked as a research intern at Microsoft Research Asiaunder the supervision of Wei Chen, and as a research assistant student at theChinese University of Hong Kong under the supervision of Shengyu Zhang.

Venue

信息管理与工程学院602室

上海财经大学（第三教学楼西侧）

上海市杨浦区武东路100号