Graph Traversal

图遍历

• 批准号: 9301186
• 负责人: Martin Tompa
• 金额: $ 21.38万
• 依托单位: University of Washington
• 依托单位国家: 美国
• 项目类别: Continuing Grant
• 财政年份: 1993
• 资助国家: 美国
• 起止时间: 1993-07-15 至 1996-12-31
• 项目状态: 已结题
• 来源: https://www.nsf.gov/awardsearch/showAward?AWD_ID=9301186&HistoricalAwards=false
• 关键词: Graph; Traversal

Graph traversal is a fundamental computational problem, not only because it is the natural abstraction of many search problems, but also because its complexity is at the root of important relationships among deterministic, non- deterministic, and probabilistic computations. There has been exciting progress made during the last few years toward understanding the complexity of graph traversal, and there are surely more breakthroughs in store very soon. This project consists of a number of integrated approaches for investigating the time and space complexity of graph traversal, including pseudo-random walks, universal traversal and reflecting sequences, and time-space tradeoffs in the rich structured setting of ``jumping automation for graphs'' (JAGs).

图遍历是一个基本的计算问题，不仅因为它是许多搜索问题的自然抽象，而且因为它的复杂性是确定性，非确定性和概率计算之间的重要关系的根源。 在过去的几年里，在理解图遍历的复杂性方面已经取得了令人兴奋的进展，而且很快就会有更多的突破。 该项目包括一些综合的方法，用于研究图遍历的时间和空间复杂性，包括伪随机游动，通用遍历和反射序列，以及在丰富的结构化设置中的时空权衡“图的跳跃自动化”（JAGs）。