Graphs and their structure: the interplay between local and global properties of graphs

图及其结构：图的局部属性和全局属性之间的相互作用

• 批准号: RGPIN-2016-05237
• 负责人: Oellermann, Ortrud
• 金额: $ 1.6万
• 依托单位: University of Winnipeg
• 依托单位国家: 加拿大
• 项目类别: Discovery Grants Program - Individual
• 财政年份: 2017
• 资助国家: 加拿大
• 起止时间: 2017-01-01 至 2018-12-31
• 项目状态: 已结题
• 来源: https://www.nserc-crsng.gc.ca/ase-oro/Details-Detailles_eng.asp?id=635545
• 关键词: Graphs; their; structure; interplay; between

Graphs serve as simple and easily understood models for various situations such as social, collaboration, communication and transportation networks as well as for chemical structures and dynamical processes. The development of graph theory has been profoundly influenced by the evolution of the internet and resulting large communication networks. Of particular interest are relationships between the global structure of the network and its local properties. A deeper understanding of the interplay between global and local properties of a network is useful in algorithmic processes. On the one hand we propose to establish new connections between global and local properties/structures of networks and on the other hand we propose to use existing connections between global and local structures of certain network types to find efficient solutions for difficult network problems. Our proposed work has four main themes as outlined below.

图作为简单且易于理解的模型，适用于各种情况，例如社交、协作、通信和运输网络以及化学结构和动态过程。图论的发展受到互联网的发展和由此产生的大型通信网络的深刻影响。特别令人感兴趣的是网络的全局结构与其局部属性之间的关系。更深入地了解网络的全局和局部属性之间的相互作用对于算法过程非常有用。一方面，我们建议在网络的全局和局部属性/结构之间建立新的连接，另一方面，我们建议使用某些网络类型的全局和局部结构之间的现有连接来寻找困难网络问题的有效解决方案。我们提出的工作有四个主题，如下所述。