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.