Parallel and Sequential Graph Search

并行和顺序图搜索

• 批准号: 9319772
• 负责人: Thomas Spencer
• 金额: $ 7.13万
• 依托单位: University of Nebraska at Omaha
• 依托单位国家: 美国
• 项目类别: Standard Grant
• 财政年份: 1995
• 资助国家: 美国
• 起止时间: 1995-01-01 至 1997-12-31
• 项目状态: 已结题
• 来源: https://www.nsf.gov/awardsearch/showAward?AWD_ID=9319772&HistoricalAwards=false
• 关键词: Parallel; Sequential; Graph; Search

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.

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