Applications of Topology to Algorithm Design

本研究计划集中在设计有效的图形 使用拓扑方法的算法。 这些方法基于 最近发展的技术和结果在拓扑图论。 提出了一种拓扑方法来获得多项式时间 解决图同构问题的有界概率算法， 这是最重要的图问题之一， 它仍然是未知的，并有许多应用。 述的方法 这里采用的是导出一个图的完全不变量， 基于拓扑和 图的组合结构。 该项目也在寻求理论的扩展， 2-连通的Whitney线性综合定理的应用 图表。 引入了图的半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.