【Independent spanning tree on interconnection networks】
时间：2013年7月11日(星期四) 上午 08:30
地点：成功楼603教室
主讲：苏州大学 樊建席 教授
主办：数计学院
Abstract: Independent spanning trees (ISTs) can be used in reliable communication protocols, one-to-all broadcasting, secure message distribution in networks. However, there is a conjecture on the existence of ISTs in networks: If a graph G is n-connected (n≥1), then there are n ISTs rooted at an arbitrary vertex in G. This conjecture has remained open for n<5. As a result, researchers have been focusing on the research on the existence and/or construction of ISTs in special networks. Bijective connection networks (BC networks, in brief) are a family of interconnection networks, which include not only the known networks such as hypercubes, crossed cubes, Möbius cubes, locally twisted cubes, etc., but also many other unknown ones. In this talk, we introduce the related work on ISTs in networks and focus on the recent results on the existence and/or construction of ISTs in special BC networks. On the other hand, we also discuss the further research on ISTs in various networks.
