Studies on Efficient Graph Algorithms

这个项目的目标是为图形优化、识别和同构问题设计有效的算法。本文主要研究了两大类图：完美图和交图。技术主要来自图论、算法设计和计算几何。经验表明，许多问题具有一些相互的潜在性质。这个项目分析问题的方法是考虑感兴趣的图形的各种表示，并制定分解或约简方案，以确定问题的核心。其目的要么是得出结论，大多数可解决的问题采用了一些众所周知的技术，要么是发现真正的新算法。

The goal of this project is to design efficient algorithms for graph optimization, recognition, and isomorphism problems. The research focuses on two large classes of graphs: perfect graphs and intersection graphs. Techniques are drawn primarily from graph theory, design of algorithms and computational geometry. Experience has shown that many problems possess some mutual underlying properties. The approach of this project in analyzing a problem is to consider various representations of the graphs in interest and to develop decomposition or reduction schemes for identifying the core of the problem. The intent is either to conclude that most solvable cases of the problem adopts some well-known techniques in a disguised manner or to discover genuinely new algorithms.