Applications of Topology to Algorithm Design

本研究计划专注于使用拓扑方法设计高效的图算法。这些方法是基于拓扑图理论中最新发展的技术和结果。图同构问题是目前复杂度未知的重要图问题之一，具有广泛的应用前景，本文提出了一种求解图同构问题的多项式时间有界概率算法。本文采用的方法是基于图的拓扑结构和组合结构的结合，推导出一个可以高效计算的图的完全不变量。该项目还寻求惠特尼的2连通图线性综合定理的理论和应用的扩展。引入图的半k连通性的概念，提出了每一个k连通图都有一个半k连通线性合成的猜想。这种扩展将为我们提供在设计高效的顺序和并行算法方面广泛应用的技术，如图连接、图嵌入和图仿真等问题。

This research program concentrates on designing efficient graph algorithms using topological methods. The approaches are based on recently developed techniques and results in topological graph theory. A topological approach is proposed to obtain a polynomial-time bounded probabilistic algorithm solving the graph isomorphism problem, which is one of the most important graph problems whose complexity still remains unknown and which has many applications. The method adopted here is to derive a complete invariant of a graph that can be computed efficiently, based on the combination of the topological and combinatorial structures of the graph. The project is also seeking an extension of the theory and applications of Whitney's linear synthesis theorem for 2-connected graphs. A concept of semi-k-connectedness of graphs is introduced, and a conjecture is proposed that every k-connected graph has a semi- k-connected linear synthesis. Such an extension will provide us with techniques that will find wide applications in designing efficient sequential and parallel algorithms for such problems as graph connectivity, graph imbedding, and graph emulation.