计算机科学中的若干组合问题研究

项目名称： 计算机科学中的若干组合问题研究

项目编号： No.61272008

项目类型： 面上项目

立项/批准年度： 2013

项目学科： 自动化技术、计算机技术

项目作者： 徐俊明

作者单位： 中国科学技术大学

项目金额： 61万元

中文摘要： 本项目主要研究互连网络可靠性和有效性分析中的若干图论参数：各种限制条件下的连通度、支撑连通度、有界连通度、Menger数、宽直径、容错直径等，它们是度量网络性能的重要参数。这些参数的研究不仅为新一代超大规模并行计算机系统的互连网络设计和分析提供进一步的数学理论基础和依据，而且进一步充实完善组合网络理论，大大丰富了图论的研究内容和应用范围。这些问题的解决和参数的确定大多是NP-hard问题，具有很大的挑战性。本项目将通过组合和代数分析方法，深入研究网络结构性质，揭示这些参数之间密切关系和内在联系，探索变化规律，力争在理论和方法上取得较大突破，实现拟定的研究目标。在项目实施过程中加强国内外学术交流，普及组合网络新理论和新方法，培养具有创新能力的高水平年轻人才，提高我国组合网络理论研究水平和国际影响。

中文关键词： 网络；图论；连通度；故障诊断；容错嵌入

英文摘要： This project aims at the study of some graphic parameters such as the conditional connectivity, spanning connectivity, bounded connectivity, Menger number, wide-diameter, fault-diameter and so on, which frequently appear in the reliable and efficient analysis of interconnection networks since they are important parameters to measure the performance of networks. Our study not only provides a further mathematical foundation for the design and analysis of the next generation of large-scale parallel super computer systems, but also further enriches and perfects combinatorial network theory, expands research contents and application areas of graph theory. The problems of determining these parameters are NP-hard, and are challenges for us. In this project, we will employ the combinatorial and algebraic method to study the structure of networks, to reveal the close relationships among these parameters and their rules of changes. To this aim, we have to make a breakthrough at some new idea and creative technique. In the process of the project, we will further promote academic intercommunion with international experts, popularize new theory and methods in networks, train young talents with innovative abilities, and upgrade our research level and international reputation in combinatorial network theory.

英文关键词： Networks；graph theory；connectivity；fault diagnosis；fault-tolerant imbedding