Dynamic algorithm: Difference between revisions
Content deleted Content added
No edit summary |
No edit summary |
||
| Line 3: | Line 3: | ||
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. |
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. |
For example, a partially dynamic graph algorithm for connectivity is allowed only insertion of edge or deletion of edge, hence its defined operation is irreversible. |
||
==References== |
==References== |
||
Revision as of 19:57, 24 November 2006
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, hence its defined operation is irreversible.
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