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.