RIA: Efficient Algorithms for Special Classes of Graphs

RIA：特殊类图的高效算法

• 批准号: 9409181
• 负责人: Hristo Djidjev
• 金额: --
• 依托单位: William Marsh Rice University
• 依托单位国家: 美国
• 项目类别: Continuing grant
• 财政年份: 1994
• 资助国家: 美国
• 起止时间: 1994-08-01 至 1997-07-31
• 项目状态: 已结题
• 来源: https://www.nsf.gov/awardsearch/showAward?AWD_ID=9409181&HistoricalAwards=false
• 关键词: RIA; Efficient; Algorithms; Special; Classes

This project focuses on the development of efficient algorithms for graphs that have small separators. The goal is to explore the particular topology of the graphs in order to improve the efficiency of the algorithms. One important class of graphs that is investigated is the class of planar graphs, which arise naturally in applications dealing with regions in the plane. The following types of problems are addressed: (1) Finding shortest paths and distances in graphs: This is a fundamental and well studied problem in computer science with many applications. The problems considered here include the design of dynamic and on-line algorithm for the single-source and the all-pairs shortest paths problems for graphs with weights on the edges; (2) Locating the center and computing the diameter of an outer planar graph: Such problems find important applications in the design and analysis of communication networks; (3) Graph separation problems: Graph separator theorems and the corresponding algorithms are important tools in the efficient solution of various combinatorial problems. Algorithms for finding separators of small cost for special classes of graphs are constructed, where the cost of the separator depends on some previously specified cost function on the edges of the graph.

这个项目的重点是为具有小分隔符的图开发有效的算法。 我们的目标是探索特定的拓扑图，以提高算法的效率。 一类重要的图是调查的平面图，这自然出现在处理区域的平面应用程序。 解决以下类型的问题： (1)在图中寻找最短路径和距离：这是计算机科学中的一个基本问题，也是一个研究得很好的问题，有许多应用。 本文所考虑的问题包括：（1）边带权图的单源最短路问题和全对最短路问题的动态在线算法设计;（2）求中心和计算直径 一个外部平面图：这类问题在通信网络的设计和分析中有着重要的应用;（3）图分离问题：图分离定理和相应的算法是有效求解各种组合问题的重要工具。 构造了寻找特殊类图的小成本分离器的算法，其中分离器的成本取决于图的边缘上的一些先前指定的成本函数。