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

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

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.