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.