Algorithmic graph theory

图是由一组节点和一组边组成的数学对象，每个边连接一对节点。图可以用来模拟许多不同类型的网络，例如蛋白质-蛋白质相互作用(PPI)网络(节点是蛋白质，两个蛋白质之间的边表示蛋白质相互作用)。图论家的第一项工作是确定在实际应用中出现的图的类型。就PPI网络而言，我们最近证明了最接近地捕捉当前可用的生物信息的模型是几何随机图，不是目前公认的无标度图。一旦确定了一个好的模型，下一步就是设计快速、易于实现的算法来解决特定模型上的各种问题。然而，正如PPI网络所预期的那样，这样的算法通常必须在巨大的数据集上工作。我的研究包括对实际中出现的受限图族的研究和设计快速实用的算法。图论中的一个基本算法概念是搜索，即遵循特定的算法访问图的所有节点和边。许多图算法包括图搜索的某个方面，最近我们确定了使用多扫描搜索算法可以最有效地解决许多其他问题。我们在基本图搜索方面的工作表明，这些搜索都具有相似的特征。我们希望这些特征将导致新的更简单的算法。

A graph is a mathematical object consisting of a set of nodes together with a set of edges, each joining a pair of nodes.  Graphs can be used to model many different types of networks, for example Protein-Protein Interaction (PPI) networks (the nodes are proteins and an edge between two proteins indicates that the proteins interact).  The first job of a graph theorist is to determine the type of graph that occurs in practical instances of the application.  In the case of PPI networks, we have recently shown that the model that most closely captures the currently available biological information is geometric random graphs, not scale-free graphs as presently accepted.  Once a good model has been identified, the next step is to design fast, easily implementable algorithms to solve various problems on the particular model.  Such algorithms often have to work on huge data sets, as anticipated for PPI networks. My research includes the study of restricted families of graphs that arise in practice and to design fast practical algorithms.  One of the fundamental algorithmic notions in graph theory is searching, i.e. following a particular algorithm to visit all nodes and edges of the graph.  Many graph algorithms include some aspect of graph searching, and we've recently determined that many other problems can be solved most efficiently using multi-sweep search algorithms.  Our work on fundamental graph searches has shown that these searches all possess similar characterizations.  We hope that these characterizations will lead to new simpler algorithms.