RIA: Efficient Algorithms for Special Classes of Graphs

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

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.