Applications of Topology to Algorithm Design

拓扑在算法设计中的应用

• 批准号: 9110824
• 负责人: Jianer Chen
• 金额: $ 3.72万
• 依托单位: Texas A&M Engineering Experiment Station
• 依托单位国家: 美国
• 项目类别: Standard Grant
• 财政年份: 1991
• 资助国家: 美国
• 起止时间: 1991-09-01 至 1994-02-28
• 项目状态: 已结题
• 来源: https://www.nsf.gov/awardsearch/showAward?AWD_ID=9110824&HistoricalAwards=false
• 关键词: Applications; Topology; 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.

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