Networks, Pattern Matching and Parallel Algorithms

这个项目涉及算法设计和分析的几个领域的一些基本问题。第一个领域是模式匹配，特别是一维字符串匹配。一个主要目标是获得字符串匹配算法性能的严格界限（在比较中测量）。二是摊开树的平摊和性能。这一努力的目的是在与展树有关的猜想上取得进一步的进展，如分裂猜想、遍历猜想和最优性猜想。第三是并行算法领域。目标是获得运行速度尽可能快的工作优化算法。描述了未来在图连通性和Voronoi图两个问题上的工作。

This project involves a number of fundamental problems in several areas of algorithm design and analysis. The first area is pattern matching and in particular, one-dimensional string matching. A major goal is to obtain tight bounds on the performance of string matching algorithms (measured in comparisons). The second is the amortization and the performance of splay trees. This effort is directed towards making further progress on conjectures relating to splay trees, conjectures such as the Split Conjecture, the Traversal Conjecture and the Optimality Conjecture. The third is the area of parallel algorithms. The goal is to obtain work-optimal algorithms which run as fast as possible. Future work on two problems, graph connectivity and Voronoi Diagrams is described.