Algorithm research at Vanderbilt focuses on graph algorithms, specifically recognition algorithms for classes of graphs with interesting representations. Some of these graph classes are used to model specific problems, while others are constructed because of theoretical properties of the class itself.
Associate Professor of Computer Science
Jeremy Spinrad's collaborative research has led to the development of the fastest known algorithms for recognizing many classes of graphs including permutation graphs, comparability graphs, circular arc graphs, circle graphs, trapezoid graphs, twodimensional partial orders, permutation graphs, weakly chordal graphs and probe interval graphs. One such project deals with probe-interval graphs, which have applications for gene sequencing. Spinrad and collaborators from Vanderbilt and the University of Colorado at Denver have designed the first polynomial time algorithm to recognize and provide a possible genetic model for these graphs. The group's current work involves investigating the possibility of reducing the time complexity and solving a particular generalization of the problem.
In addition to his current work, Spinrad was the primary person responsible for developing a theory he calls robust algorithms. He was also involved in the development of certifying algorithms, which are algorithms that produce a certificate of their correctness on the given input as part of the output.