Structural and Algorithmic Aspects of Graphs

图的结构和算法方面

• 批准号: RGPIN-2017-04053
• 负责人: Huang, Jing
• 金额: $ 1.02万
• 依托单位: University of Victoria
• 依托单位国家: 加拿大
• 项目类别: Discovery Grants Program - Individual
• 财政年份: 2019
• 资助国家: 加拿大
• 起止时间: 2019-01-01 至 2020-12-31
• 项目状态: 已结题
• 来源: https://www.nserc-crsng.gc.ca/ase-oro/Details-Detailles_eng.asp?id=675447
• 关键词: 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.******My long-term goal is an on-going study of combinatorial problems from both the structural and computational points of view. The P vs NP problem is considered to be very difficult at the moment. I anticipate a theory will be developed along the way in finding a solution to this difficult problem. I would like to make contributions toward establishing such a theory. My objectives are therefore to continue producing mathematical results concerning the structure of combinatorial objects and using the structural properties to derive dichotomy type of theorems, which hopefully will form building blocks for the anticipated theory.******Graph searching is fundamental in exploring graphs and detecting their structures. Deciding which vertices of a graph can be end-vertices of a specific graph search is a problem that has been actively studied in the recent years. Several results which characterize end-vertices of certain searches have been obtained for some classes of graphs. However, the end-vertex problem is still open for many classes of graphs.******Graph structures are sometimes inherent in their orientation properties; certain graphs can only admit certain orientations. Deciding whether a partially oriented graph can be completed to an oriented graph that satisfies a prescribed property is a fundamental problem which generalizes several existing problems. ******Graph colouring is a central topic in graph theory and has applications in real life. Colouring problems are special partition problems which are hard in general. Discovering graph classes for which these problems admit efficient algorithmic solutions is desirable and has potential applications in real life. ******As short-term objectives, I will continue studying these three types of problems, i.e., end-vertex problems of various graph search algorithms, orientation completion problems, and generalized graph colouring problems.*****

*我的研究兴趣在于计算组合学，它主要处理有限对象。我花了大部分时间研究的对象是图形。许多有实际意义的问题，如任务调度、通信网络设计、交通控制等，都可以用图来建模。问题的有效计算解通常可以从对图的结构属性的理解中推导出来。图论在许多其他科学中也被证明是有用的。例如，计算机科学与图论密切相关。开发高效的算法来解决图上的问题是计算机科学家的主要兴趣。当然，并不是所有关于图的问题都被证明是有效的算法。人们普遍认为，某些问题不会得到有效的解决方案，但要证明这一点，本身就是一个问题。克莱数学研究所设立的P与NP问题正是反映了这种情况。我的长期目标是从结构和计算的角度对组合问题进行持续的研究。目前，P与NP问题被认为是非常困难的。我预计，在寻找这个难题的解决方案的过程中，将会发展出一种理论。我愿意为建立这样的理论做出贡献。因此，我的目标是继续产生关于组合对象结构的数学结果，并利用结构性质来推导二分型定理，这些定理有望形成预期理论的基础。*图搜索是探索图和检测其结构的基础。确定一个图的哪些顶点可以是特定图搜索的终点是近年来活跃研究的一个问题。对于某些图类，已经得到了一些刻画某些搜索的端点的结果。然而，对于许多类型的图，端点问题仍然是开放的。*图的结构有时是其定向性质所固有的；某些图只允许某些定向。判定一个部分有向图是否能完全化为满足一定性质的有向图是一个基本问题，它概括了已有的几个问题。*图着色是图论中的一个中心问题，在现实生活中有着广泛的应用。着色问题是一般难以解决的特殊划分问题。发现这些问题允许有效算法解的图类是可取的，并且在现实生活中具有潜在的应用。*作为短期目标，我将继续研究这三类问题，即各种图搜索算法的末端顶点问题、方向完成问题和广义图着色问题。*