Parallel and Sequential Graph Search

这项研究集中在发现关于图的信息的算法上。要发现图表中几乎所有有趣的东西，有必要查看整个图表。另一方面，还有一些重要的顺序算法，它们的运行时间与输入图的大小成正比。其中两个算法解决了(A)寻找深度优先的生成树和(B)寻找宽度优先的生成树的问题。这项研究试图回答两个问题：(1)这些算法解决的问题可以多快、多有效地并行解决？(2)这些问题的几个实例，在同一个图上，但具有不同的起始顶点，是否可以用一种比单独解决每个实例更有效的技术来解决？对第二个问题的肯定回答将导致更快的算法来找到图的直径，这是网络设计中的一个重要问题。

This research concentrates on algorithms that discover information about graphs. To discover almost anything interesting about a graph it is necessary to look at the whole graph. On the other hand, there are important sequential algorithms whose running time is proportional to the size of the input graph. Two of these algorithms solve the problems (a) of finding a depth-first spanning tree and (b) of finding a breadth-first spanning tree. This research seeks to answer two questions: (1) How quickly and efficiently can the problems that these algorithms solve be solved in parallel? (2) Can several instances of these problems, on the same graph, but with different starting vertices, be solved by a much more efficient technique than just solving each instance separately? An affirmative answer to the second question will result in a faster algorithm that finds the diameter of a graph, an important problem in network design.