Completely Independent Spanning Trees: Applications and Algorithms
报告题目(Title)：Completely Independent Spanning Trees: Applications and Algorithms
报告人(Speaker)：张肇明（台北商业大学）
地点(Place)：后主楼1124
时间(Time)：2019年11月8日 16：00-17:00
邀请人(Inviter)：徐敏
报告摘要
For the underlying graph G of a network, a set of k(> 2) spanning trees of G are called completely independent spanning trees (CISTs for short) if they are mutually inner-node-disjoint. In particular, if k = 2, the two CISTs are called a dual-CIST. It is well-known that determining the existence of a dual-CIST in a graph is an NP-complete problem. Kwong et al. [IEEE/ACM Trans. Networking, vol.19, pp.1543–1556, 2011] defined that a routing is a protection routing if there is an alternate with loop-free forwarding when it occurs a single link or node failure. Tapolcai [Optim. Lett., vol.7, pp.723–730, 2013] showed that a network possessing of a dual-CIST suffices to establish a protection routing. In this talk, we introduce the concept of protection routing with security, called secure-protection routing, such that the routing is not only protected but also secure, i.e., no other node except the destination in the network transmission can receive the complete message. We show that the secure-protection routing can be configured in a network provided its underlying graph admits three CISTs. Accordingly, we develop a tree searching algorithm called two-stages tree-searching algorithm (abbreviated as TS^2 ), to construct three CISTs of a 6-regular graph if the scale of the graph is not too large and it exists three CISTs for certain. In particular, we demonstrate that three CISTs of LTQ_6 and CQ_6 can be acquired by using TS^2. Moreover, for highdimensional LTQ_n and CQ_n with n > 7, we show that their three CISTs can be constructed by recursion.
