Structural and Algorithmic Aspects of Graphs

图的结构和算法方面

• 批准号: RGPIN-2017-04053
• 负责人: Huang, Jing
• 金额: $ 1.02万
• 依托单位: University of Victoria
• 依托单位国家: 加拿大
• 项目类别: Discovery Grants Program - Individual
• 财政年份: 2017
• 资助国家: 加拿大
• 起止时间: 2017-01-01 至 2018-12-31
• 项目状态: 已结题
• 来源: https://www.nserc-crsng.gc.ca/ase-oro/Details-Detailles_eng.asp?id=635183
• 关键词: Structural; Algorithmic; Aspects; Graphs

My research interest lies in computational combinatorics, which deals with mostly finite objects. The type of objects that I spent most of time studying are graphs. Many problems of practical interest, such as scheduling of tasks, communication network design, traffic control, etc., can be modelled by graphs. Efficient computational solutions of problems can often be derived from an understanding of the structural properties of graphs. The theory of graphs has also proven to be useful in many other sciences. Computer science, for example, is very closely related to graph theory. Developing efficient algorithms to solve problems on graphs is of major interest to computer scientists. Of course, not all problems on graphs have been shown to admit efficient algorithms. It is generally believed that certain problems do not admit efficient solutions, but to prove this is the case is a problem by itself. The P vs NP problem, established by Clay Mathematics Institute as one of the Millennium Prize Problems, reflects exactly this situation.

我的研究兴趣在于计算组合学，它主要处理有限对象。我花了大部分时间研究的对象类型是图表。许多实际问题，如任务调度、通信网络设计、交通控制等，都可以用图来建模。问题的有效计算解决方案往往可以从对图的结构性质的理解中得到。图论在许多其他科学中也被证明是有用的。例如，计算机科学与图论密切相关。开发有效的算法来解决图上的问题是计算机科学家的主要兴趣。当然，并不是所有图上的问题都有有效的算法。人们普遍认为某些问题没有有效的解决办法，但要证明这一点本身就是一个问题。克莱数学研究所（Clay Mathematics Institute）作为千禧年奖问题之一提出的P vs NP问题，正是反映了这种情况。