Dynamic algorithms allow the user to maintain some property while
making changes to the input. For example, a minimum spanning tree
might be maintained while edges are inserted and deleted from
a graph. The hope is that such updates will be much more efficient
than executing a minimum spanning tree algorithm from scratch.
In a kinetic algorithm the data can change continuously -- e.g.,
an edge weight might increase over time. There has been significant
research in the past twenty years on dynamic and kinetic algorithms
for many problems. [1] Furthermore, in recent years there has
been a significant increase in the need for these sorts of algorithms
in various applications. Examples include maintaining properties
of moving sets of points in various simulations, and maintaining
various properties of a communication network (e.g., shortest
paths and connectivity) as connections are added and deleted.
We are interested in developing efficient implementations of dynamic
and kinetic algorithms. This work is partially based on recent
results on semi-automatically converting static algorithms to
dynamic algorithms by maintaining dependences. This can greatly
reduce the cost of coding dynamic algorithms. We plan to experiment
with these techniques and compare them with more traditional algorithms
for the same problem.
[1] D. Eppstein, Z. Galil, and G. F. Italiano,
Dynamic graph algorithms, In CRC Handbook of Algorithms
and Theory of Computation, Chapter 22, CRC Press, 1997.
Preliminary
Presentation (ppt),
(pdf)
Other Mini-PROBEs for Summer 2003
Algorithms for Facility Location
Anonymous Communication
Designing Overlay Multicast Networks for Streaming
HumanAUT
Moving Mesh Simulations
Space-Efficient
Point Location
CENTER
Carnegie
Mellon 
Mini-PROBE: Dynamic Algorithms
Aladdin
