Dynamic algorithm: Difference between revisions
Content deleted Content added
No edit summary |
tagging as uncategorized using AWB |
||
| Line 1: | Line 1: | ||
{{uncat|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. |
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. |
||
Revision as of 13:29, 27 November 2006
 | This redirect has not been added to any content categories. Please help out by adding categories to it so that it can be listed with similar redirects. |
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