Applications of Topology to Algorithm Design

点击翻译按钮获取中文摘要

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.