终检评审通过 创新训练 416自然科学相关工程与技术 理论研究-科学技术国家级

由于网络硬件的快速进步，大规模集成电路的出现，大规模的多处理器系统已经在人类生活中服务，并发挥着越来越重要的作用。系统中处理器之间的连接模式称为该系统的互连网络(简称网络)。网络本质上刻画了系统的结构特征，而图论是研究和分析网络的最基本和强有力的数学工具。为方便已有通信模式的算法的兼容和移植，同时减少网络的拥塞和负载，在网络设计和评估过程中，一个核心问题就是判断一些已知的网络能否嵌入到这个网络中。此处提到的嵌入是指同构嵌入，用图论的语言描述，即为图中是否存在某些特殊的图作为其子图，也称图的(同构)嵌入。 CISTs，即完全独立支撑树，在并行计算机容错广播以及路由安全保护中具有重要应用，得到了研究者们的广泛关注和研究。确定网络中是否存在多棵CISTs是NP-难问题。因此，在对网络CISTs的研究中，往往需要对网络进行限制。近年来，对一些具有广泛应用的特殊网络，如超立方体网络和局部扭立方体网络等，研究者陆续提出一些嵌入CISTs的算法。网络的直径是指网络中任何一对节点之间的最大距离，它表示在网络中执行一些基本操作，如一对一路由、广播、数据聚合等，所需时间的最坏情况下界。为了实现理论上的下界，在网络嵌入CISTs的研究中，面临的一个挑战就是追求减少树的高度或直径的目标。本项目计划以一些特殊网络作为研究对象，围绕网络中嵌入低直径CISTs算法进行研究。