RIA: Efficient Algorithms for Special Classes of Graphs

这个项目的重点是开发具有小分隔符的图形的高效算法。目标是探索图的特定拓扑结构，以提高算法的效率。研究图的一个重要类别是平面图，它在处理平面区域的应用中自然出现。(1)在图中找到最短的路径和距离：这是计算机科学中一个基本的、研究得很好的问题，有很多应用。这里考虑的问题包括单源问题的动态在线算法设计和边上有权的图的全对最短路径问题；(2)外平面图的中心定位和直径计算：这类问题在通信网络的设计和分析中有重要的应用；(3)图分离问题：图分离定理及其算法是有效求解各种组合问题的重要工具。构造了寻找特殊图类的小代价分隔符的算法，其中分隔符的代价依赖于图边缘上的某个先前指定的代价函数。

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.