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.