RIA: Depth-First Search as a Divide-and-Conquer Tool

RIA：深度优先搜索作为分而治之的工具

• 批准号: 8909323
• 负责人: Ming-Yang Kao
• 金额: $ 1.37万
• 依托单位: Indiana University
• 依托单位国家: 美国
• 项目类别: Standard Grant
• 财政年份: 1989
• 资助国家: 美国
• 起止时间: 1989-07-01 至 1990-05-21
• 项目状态: 已结题
• 来源: https://www.nsf.gov/awardsearch/showAward?AWD_ID=8909323&HistoricalAwards=false
• 关键词: RIA; Depth; First; Search; Divide

A separator of a graph is a set of vertices whose removal breaks the graph into small pieces. A cycle separator is a simple cycle whose vertices form a separator. Finding separators is an essential part of divide-and-conquer strategies for many graph-theoretic applications. The PI has recently discovered that, surprisingly, every graph has a cycle separator and such a cycle separator can be efficiently computed by depth-first search in sequential and parallel computations. Consequently, depth-first search now assumes a new role as a divide- and-conquer tool. This linkage between cycle separators and depth- first search has never been available before, and promises to bring about unconventional applications of depth-first search. This project is intended to explore new possibilities opened up by the search- separator linkage.

图的分隔符是一组顶点，移除这些顶点会将图分割成小块。循环分隔符是顶点形成分隔符的简单循环。在许多图论应用中，寻找分隔符是分而治之策略的重要组成部分。PI最近发现，令人惊讶的是，每个图都有一个循环分隔符，这样的循环分隔符可以通过顺序和并行计算中的深度优先搜索来高效地计算。因此，深度优先搜索现在承担了一个新的角色，即分而治之的工具。这种循环分隔符和深度优先搜索之间的联系以前从未出现过，并有望带来深度优先搜索的非常规应用。该项目旨在探索搜索-分隔符链接带来的新可能性。