Search Based Graph Algorithms

点击翻译按钮获取中文摘要

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.**