Dynamic algorithm: Difference between revisions

Content deleted Content added

Inline

Revision as of 02:33, 3 January 2007

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

@@ Line 1: / Line 1: @@
+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.
-{{uncat|November 2006}}
+The goal of '''dynamic algorithms''' is to efficiently update the solution of problem after [[dynamic change]]s. 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.
-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.
@@ Line 10: / Line 8: @@
 * D. Eppstein, Z. Galil, and G. F. Italiano. [http://citeseer.ist.psu.edu/eppstein99dynamic.html Dynamic graph algorithms]. In CRC Handbook of Algorithms and Theory of Computation, Chapter 22. CRC Press, 1997. 95
+[[category: algorithms]]