Efficient Graph Algorithms and Data Structures - Theory and Practice

算法是计算机科学的核心。这项研究的目标是为一系列重要和有趣的算法问题设计和分析算法，这些问题主要选自图形和网络领域。理想的做法是获得在理论和实践上都很高效、概念上也很简单的算法--简而言之，“优雅”的算法。对于每个问题，都将对可能的解决办法进行系统的探索。要研究的具体问题将从动态拓扑排序和相关问题、平面性测试和相关图问题和数据结构、最大和最小代价网络流问题、二叉搜索树和相关数据结构的摊余效率、寻找支配者及相关问题等中选择。这项研究的广泛影响将是为特定算法问题和问题族的解决方案的设计空间提供新的曙光，产生新的算法和分析技术，提供新旧算法的有效实施，并产生它们的经验表现的比较。此外，将对算法设计领域的研究和教学界的新成员进行培训，并将开发新的方法和新的材料来交流该领域的重要概念。

Algorithms are at the core of computer science. The goal of this research is to design and analyze algorithms for a selection of important and interesting algorithmic problems, chosen primarily from the area of graphs and networks. The ideal is to obtain algorithms that are efficient in theory and practice, and conceptually simple as well -- in short, "elegant" algorithms. For each problem, a systematic exploration of possible solutions will be undertaken. Specific problems to be studied will be selected from among dynamic topological ordering and related problems, planarity testing and related graph problems and data structures, maximum and minimum cost network flow problems, amortized efficiency of binary search trees and related data structures, finding dominators and related problems, and others. The broad impact of the research will be to shed new light on the design space of solutions for specific algorithmic problems and families of problems, to produce new algorithmic and analytical techniques, to provide efficient implementations of old and new algorithms, and to produce comparisions of their empirical performance. In addition, new members of the research and teaching community in the field of algorithm design will be trained, and new approaches and new materials for communicating the important concepts in the field will be developed.