Algorithms Research Page:
Overview
At Vanderbilt, research on algorithms primarily deals with graph algorithms, and issues arising from the study
of graph algorithms. A particular area of specialization is recognition algorithms
for special classes of graphs. Many graph classes have been constructed in
the literature, some because the graph class has been used to model specific
problems, and others simply because
of nice theoretical properties of the class itself. This research has lead to the development of the fastest
known algorithms for recognizing such graph classes as comparability graphs,
circular-arc graphs, circle graphs, permutation graphs, weakly chordal graphs,
probe-interval graphs, and trapezoid graphs.
Topics
- Robust Algorithms: There is a surprising ambiguity in what it means
to say that you have "solved" a problem on a particular class
of inputs, which arises particularly if there is no polynomial algorithm
to determine whether an input is in the class. We introduce the notion of
a robust algorithm for solving an input in a restricted domain; such an
algorithm may either solve the problem correctly (whether or not the input
is in the domain) or answer that the input is not in the domain. This leads
to new definitions of intractability for a domain, as well. There are a
large number of open problems, both dealing with specific problems and domains
and on more general issues involving proving intractability. J. Spinrad
and V. Raghavan.
- Graph Representations: This research deals with questions about
how a class of graphs can be represented in a computer. If a graph class
is sufficiently small, there are often better ways to represent the class
than by general structures such as adjacency matrices and lists. Open problems
involve both finding good representations of specific graph classes, and
general conjectures regarding representability of all classes of graphs.
- Graph Problems Connected to Matrix Multiplication: This project
deals with the time complexity of certain algorithms on graphs. We have
been able to reduce the time complexity of a number of well known problems
(finding clique cutsets, star cutsets, two-pairs, asteroidal triples, and
others) using fast matrix multiplication algorithms as subroutines. We have
also given evidence that some of these may truly be tied to matrix multiplication,
in that finding efficient algorithms without using matrix multiplication
would require a major breakthrough. Open problems involve reducing the time
complexity of problems, and providing stronger evidence of the link between
these problems and matrix multiplication. Joint work between J. Spinrad and Dieter Kratsch
of the University of Metz.
- Probe-Interval Graphs: This research deals with a class of graphs
which arise in the context of gene sequencing. We have designed the first
polynomial time algorithm to recognize and provide a possible genetic model
for these graphs. Current work involves attempts to reduce the time complexity,
and to solve a particular generalization of the problem. Joint work between
J. Spinrad,
Julie Johnson, and Ross McConnell of the University of Colorado at Denver.
- Clique-width: There has been considerable recent interest in a
type of graph called bounded clique-width graphs, because many problems
which are difficult in general can be solved on graphs with bounded clique-width.
In previous papers, solving problems on bounded clique-width graphs required
that the input graph was given in a particular form which constituted a
proof that the graph had bounded clique-width; thus, the algorithms were
not usable on a general graph which happened to have bounded clique-width.
We have shown that many of these problems can be solved even if the input
is given in standard adjacency matrix form. J. Spinrad, Vijay Raghavan,
and Julie Johnson.
Faculty
Jerry Spinrad
Top of Page - EECS
Home - VUSE - Vanderbilt
Home
