Dynamic algorithm: Difference between revisions

Most of algorithms are static in the sense that the recorded information will destruct after solving the problem, but sometimes people want to maintain some properties and need algorithms working as monitors.

The goal of dynamic algorithms is to efficiently update the solution of problem after dynamic changes. There are two kinds of dynamic algorithms, one is partially dynamic if the defined operations are irreversible, and the second kind is fully dynamic if the defined operations are reversible.

For example, a partially dynamic graph algorithm for connectivity is allowed only insertion of edge or deletion of edge.

References

• 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. 95