Structural and Algorithmic Aspects of Graphs

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

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.