Dynamic graph algorithms are algorithms that maintain information about properties of a graph, while the graph is changing.
The paper "Randomized Dynamic Graph Algorithms with Polylogarithmic Time per Operation" presents a fully dynamic connectivity algorithm, i.e. a data structure is maintained so that queries of the form "Is node i connected to node j?" can be answered quickly, without having to recompute connectivity for the whole graph after each update of the graph. The Las Vegas algorithm requires no more than logarithmic time for queries and polylogarithmic amortized expected time per update. The best previously known algorithm due to G. Fredrickson (1985), as improved by D. Eppstein, Z. Galil, G. Italiano, and A. Nissenzweig (1992) were much more costly per update ( O(n^{1/2}), where n=number of nodes in the graph) and more difficult to implement. This was joint work with M. Henzinger.
As a consequence of our connectivity algorithm, we are able to solve several other dynamic graph problems with polylogarithmic update time and polylogarithmic query time, including bipartiteness, approximate minimum spanning tree, and the k-edge witness problem. Using similar techniques we have developed polylogarithmic algorithms for biconnectivity with bounded degree (FOCS '95) and 2-edge connectivity ``Fully Dynamic 2-Edge Connectivity in Polylogarithmic Time per Operation'' . No previous polylogarithmic time algorithms were known for these problems.
We also developed a fully dynamic method of maintaining the minimum spanning trees deterministically which is simple and runs faster than previously known algorithms (O(n^{1/3}) amortized update time) ("Maintaining Minimum Spanning Trees in Dynamic Graphs" ) .
For directed graphs, in 1995, using different randomized techniques, we developed the first fully dynamic Monte Carlo algorithm which does better than recomputation from scratch for answering queries as to whether there's a directed path from one vertex to another (FOCS'95) (i.e. maintaining the transitive closure). However, query costs were expensive (O(n/log n).
Revisiting this problem in 1999, in "A Fully Dynamic Algorithm for Maintaining the Transitive Closure," G. Sagert and I presented the first fully dynamic Monte Carlo algorithm for maintaining the transtive closure with constant query time. The update time is O(n^(2+a)) where a=min {maximimum size of a strongly connected component, .25...). In ``Fully Dynamic Algorithms for Maintaining All-Pairs Shortest Paths and Transitive Closure,'' , I presented the first fully dynamic algorithm for maintaining all-pairs shortest paths in directed graphs, and well as a deterministic dynamic transitive closure algorithm. Approximately shortest paths and also transitive closure can be maintained in O(n log n) time per update.
My Ph.D. student Lou Ibarra , is working on dynamic
graph properties for chordal and interval graphs.
(A) Biologists need to measure distances between evolutionary trees,
when comparing different biological theories. In 1978,
two prominent computational biologists, T. Smith and M. Waterman,
defined a measure of distance between two trees known
as the nni distance or the number of
``nearest neighbor interchanges'' which turns out to have an essentially
equivalent formulation in computer science as the number
of tree rotations needed to turn one parenthesized arithmetic expression
into another.
No way to effectively compute this distance is known, yet several approximation
methods methods (Smith-Waterman, Brown-Day) were believed
effective. My work with T. Warnow, presented at a DIMACS workshop
shows a family of pairs of trees for which these methods give an asymptotically
higher estimate than the actual distance.
(B) Given a set of evolutionary trees whose leaves are labelled with
a subset of possible species, the tree consensus problem is
to determine if a consensus tree exists which is homeomorphic
to the given trees and if so, construct it.
The consensus tree problem first arose in computer science in work
by A. Aho, et. al. because of its applications
to the theory of relational data bases.
We devised
a method of speeding up the Aho algorithm using a
novel dynamic graph data structures to the problem (``Constructing a Tree from Homeomorphic Subtrees with
Applications to Computational Biology'' ).
Paper
``Limits on the power of parallel random access machines with
weak forms of write conflict resolution'' proves
lower bounds
in a very weak model for
a parallel machine with random access shared memory in which
any number of processors may read from and write to the same cell in a
single step (CRCW PRAM).
In this model, the adversary may arbitrarily fix the contents of
the cell when more than one processor writes to it.
We also show a randomized algorithm that achieves expected times which are
asymptotically smaller than our deterministic lower bounds.
The ``set-maxima'' problem,
was stated in a paper by R. Graham, A. Yao,
and F. Yao, in a section attributed to Fredman in
1980. (The problem didn't have a name at the time.)
The set-maxima problem was given as a example of a problem with a
``weak'' information theory lower bound.
Given a collection of (possibly overlapping) sets whose elements are
drawn from a total order, the problem is
to determine the aximum element in each set,
where cost is measured by the number of comparisons
between elements needed by an adaptive strategy. No known method other than the
trivial one of finding each maximum element
from each separately was known until the randomized algorithm of Kenyon and mysel
f
in a paper in STOC'89. In that paper, we were solving the set-maxima
problem in an attempt to verify a partial order, a problem raised by A. Yao.
Paper
Optimal Randomized Algorithms for Local Sorting and Set-Maxima"
improves that result, giving
a randomized algorithm for set-maxima, whose expected cost matched the
information theory bounds for the problem.
A special case of the set-maxima problem occurs in the problem of
of determining whether a given spanning tree is a minimal
spanning tree. In 1984, J. Komlos gave a deterministic algorithm which uses
a linear number of comparisons,
though no data structure to allow a linear time
implementation of his method was known.
In my paper "A Simpler Linear Time Algorithm for Minimum Spanning
Tree Verification"
I simplify his algorithm and give
a linear time (determinisitic) implementation in the unit cost RAM model.
This technique is simpler and more constructive than the previous
linear time technique of M. Henzinger.
This minimum spanning tree
algorithm is a subroutine in the first linear expected time
algorithm for computing the minimum spanning tree, due to D. Karger, P. Klein an
d
R. Tarjan.
The maximum flow problem was done while at NEC Research Institute, with
S. Rao and R. Tarjan.
Our paper "A Faster Deterministic Maximum Flow Algorithm"
gives what is the best to my knowledge the
asymptotically fastest deterministic algorithm for the maximum flow problem.
This paper
appeared in a special issue of outstanding papers of SODA 92
in the Journal of Algorithms.
The paper derandomizes a technique of Cheriyan, Hagerup, and Mehlhorn.
My thesis, and papers
"An Omega(n^{5/4) Lower Bound on the Randomized
Complexity of Graph Properties",
A Lower Bound for the Recognition of Digraph Properties,
"Boolean Functions with Noisy
Nodes"
concern the Boolean decision tree model. In that model,
the cost of
evaluating a function is measured by the number of bits of
input which
must be examined to determine its value, in the worst case, with an
adaptive strategy.
This model provides a simple context in which to study the effects
of randomization, "noisy" information, and other aspects of computation.
A lower bound in this simple model provides lower bounds for more sophisticated
models of computation.
This area of study
was motivated by the problem of proving lower bounds for graph problems
when the graph is given as an adjacency matrix.
The 1973 Aanderaa-Rosenberg Conjecture
postulated a certain lower bound on the number of queries to the adjacency
matrix of a graph required to determine if the graph had any given monotone
graph property. This conjecture sparked a number
of papers in the area. A brief survey of work
in this area can be found in
the Handbook of Theoretical Computer Science, pp.532-536.
My thesis work extended the techniques of Kahn, Saks, and Sturtevant
to improve the deterministic lower bound for directed graphs.
It also substantially improved the known lower bound for the randomized
complexity
of monotone graph properties, a problem posed by A. Yao.
A third chapter, never published, extended these results to the case
where error is allowed.
Some years later, I revisited this area with C. Kenyon,
of the Ecole Normale Superior in Lyon, and looked at computation where
queries were assumed to be ``noisy,'' meaning faulty with some fixed
probability. My work was inspired by a paper by U. Feige, D. Peleg,
P. Raghavan and E. Upfal who
had shown that the problem of designing tournaments to determine the
best basketball team was an interesting problem when one could only
assume that the better team would win with some fixed probability greater
than $1/2$. This lead to our development of an algorithm to
evaluate any Boolean function when each reading of an input bit
has a fixed probability of error.
Computational biology
Lower bounds in parallel machines
Set-maxima problem and the verification of partial orders
and minimum spanning trees
Maximum flow problem
Boolean decision trees