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.