Search Based Graph Algorithms

“图”，也称为“网络”，由一组节点和一组边组成，每条边连接一对特定的节点。例如，考虑一个特定班级学生的社交网络。班上的每个学生都是图/网络中的一个节点。连接节点对的边可以表示相互友谊，在这种情况下边没有方向，或者在边定向的情况下表示一个方向的友谊。给出这样的友谊网络，我们可能希望找到朋友的“集团”，即节点集合，使得集团中的每个人都是与集团中的其他所有人的朋友。对于计算机科学家来说，设计一种在图中找到这样一个集团的算法是一项典型的任务--希望这样的算法应该是高效的，并且易于实现。 最基本的图算法范例之一是“图搜索”，其中算法遵循访问图的所有顶点的规定方法。这种搜索算法是在19世纪90年代末开发出来的，目的是解决迷宫问题。最近已经表明，许多图问题可以通过使用图搜索来解决，并且目前正在发现新的搜索类型。 我的研究涉及寻找这样的基于图搜索的算法；搜索通常以多扫描的方式使用，一个搜索的输出用作下一个搜索的输入。

A "graph", also called a "network" consists of a set of nodes together with a set of edges, each edge joining a particular pair of nodes. For example, consider a social network on students in a given class. Each student in the class is a node in the graph/network. The edges joining pairs of nodes could represent mutual friendship in which case the edges have no direction, or one directional friendship in which case the edges are directed. Given such a friendship network, we may wish to find "cliques" of friends, namely sets of nodes such that each person in the clique is a friend with everyone else in the clique. Designing an algorithm to find such a clique in a graph is a typical task for computer scientists - hopefully, such algorithms should be efficient and easy to implement. One of the fundamental graph algorithmic paradigms is "graph searching" where the algorithm follows a prescribed method of visiting all vertices of the graph. Such search algorithms were developed in the late 1890s to solve maze problems. Recently it has been shown that many graph problems can be solved by using graph searching and new types of searches are currently being found. My research involves finding such graph searching based algorithms; often searching is used in a multi-sweep fashion where the output of one search serves as the input for the next search.