Algorithmic graph theory

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

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.