Skip to main content

Electrical Engineering and Computer Science

Algorithm Research

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.

Algorithm Research

Jeremy Spinrad Jeremy Spinrad

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.