James S. McDonnell Distinguished University Professor
Princeton University
Abstract: Efficient algorithms for many problems rely on the proper choice of data structures. An interesting example of this is the problem of finding dominators in a directed graph. The dominators problem arises in global computer code optimization, hardware verification, and food web analysis, among other places. I'll describe work done on this problem and on related data structures over the last 40 years. Even though the problem has been heavily studied for a long time, new discoveries continue to be made.
Biography: Robert Tarjan is the James S. McDonnell Distinguished University Professor of Computer Science at Princeton University, and a senior fellow at Hewlett-Packard. His research is in the field of algorithms and data structures. He has developed linear time algorithms for testing a host of graph properties including planarity and multiconnectivity. His closely related work on efficient data structures has led to splay trees, persistent data structures and Fibonacci heaps, among others.