Structural and Algorithmic Aspects of Graphs

图的结构和算法方面

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

我的研究兴趣在于计算组合学，它主要处理有限对象。我花大部分时间研究的对象类型是图形。许多实际问题，如任务调度、通信网络设计、流量控制等，都可以用图表来表示。问题的有效计算解决方案通常可以从对图的结构性质的理解中得出。图论在许多其他科学中也被证明是有用的。例如，计算机科学与图论有着非常密切的关系。开发有效的算法来解决图上的问题是计算机科学家的主要兴趣。当然，并不是所有的图上的问题都有有效的算法。人们普遍认为，某些问题不承认有效的解决方案，但要证明这是一个问题本身。由Clay数学研究所设立的千禧年奖问题之一的P vs NP问题正是这种情况的反映。我的长期目标是从结构和计算的角度对组合问题进行持续的研究。P vs NP问题目前被认为是非常困难的。我预料在解决这个难题的过程中会沿着发展出一种理论。我想为建立这样一个理论做出贡献。因此，我的目标是继续生产有关组合对象的结构的数学结果，并使用的结构特性，以获得二分法类型的定理，这希望将形成预期的理论积木。图搜索是在探索图形和检测其结构的基础。决定图的哪些顶点可以是特定图搜索的端顶点是近年来一直在积极研究的问题。对于某些图类，已经得到了几个刻画某些搜索的端点的结果。然而，许多图的端点问题仍然是开放的。图的结构有时是固有的，在其方向属性;某些图只能承认某些方向。判定一个部分有向图是否可以完备为满足给定性质的有向图是一个基本问题，它是现有问题的推广。图着色是图论中的一个中心课题，在真实的生活中有着广泛的应用。着色问题是一种特殊的划分问题，一般来说比较困难。发现这些问题允许有效算法解决方案的图类是可取的，并且在真实的生活中具有潜在的应用。作为短期目标，我将继续研究这三类问题，即，各种图搜索算法的端点问题、方向完成问题和广义图着色问题。