SPEAKER: Fan Chung Graham
UC San Diego (CSE and Math)
In recent years, a variety of graph optimization problems have arisen in which the graphs involved are much too large for the usual algorithms to be effective. Furthermore, often only partial information is available and the graph may be changing dynamically as well. In this talk, we will examine one of the fundamental problems of this type. Suppose that we are given the distances between the nodes in a (relatively small) subset of the graph. How much can we learn about the entire graph from this limited information? We will discuss the complexity of such problems and the performance of the corresponding approximation algorithms. The connections with various applications such as Internet tomography and computational biology will be illustrated and future directions/problems will be mentioned.
(This is a joint work with Mark Garrett, Ronald Graham and David Shallcross)