Efficient Graph Algorithms and Data Structures - Theory and Practice

Princeton University, Princeton NJ

Investigators

Abstract

Algorithms are at the core of computer science. The goal of this research is to design and analyze algorithms for a selection of important and interesting algorithmic problems, chosen primarily from the area of graphs and networks. The ideal is to obtain algorithms that are efficient in theory and practice, and conceptually simple as well -- in short, "elegant" algorithms. For each problem, a systematic exploration of possible solutions will be undertaken. Specific problems to be studied will be selected from among dynamic topological ordering and related problems, planarity testing and related graph problems and data structures, maximum and minimum cost network flow problems, amortized efficiency of binary search trees and related data structures, finding dominators and related problems, and others. The broad impact of the research will be to shed new light on the design space of solutions for specific algorithmic problems and families of problems, to produce new algorithmic and analytical techniques, to provide efficient implementations of old and new algorithms, and to produce comparisions of their empirical performance. In addition, new members of the research and teaching community in the field of algorithm design will be trained, and new approaches and new materials for communicating the important concepts in the field will be developed.