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.
