I was told my explanations weren't very clear so here it goes with more details, a much simpler example and explicit links
A dynamic graph algorithm is a classical graph algorithm (say all-pairs shortest path) that is able to update the result when there is a small modification of the input without computing everything from scratch. Typical usage are large networks, for instance adding a fiber optic cable in a suburb of Paris won't change the shortest path between New York and San Francisco, therefore computing everything from scratch again is unnecessary.
There are 2 ways of achieving that result
- recomputation : pretty much like backtracking debuggers in functional languages, they "save" a previous state and re-execute the computation tree/DAG from there
- dedicated algorithm that "fix" the result in place : STOC / FOCS like algorithms
Lets take a very simple example fun f a b c -> f a + f b + f c
The computation tree is something like
evaluate f a
evaluate f b
evaluate f c
evaluate f a + f b + f c
if now there is a small change in a, say a -> 'a the backtracking algorithms will do the following
evaluate f 'a
read f b from memory
read f c from memory
evaluate f 'a + f b + f c
the typical problems to solve are similar to backtracking debuggers in functional languages : efficiently save intermediate states, optimise fully reversible transformations, etc.
Umut Acar with his self-adjusting ML is a typical representative of that kind of work as well as backtracking debuggers (Caml, SML)
A dedicated algorithm instead will use the mathematical properties of the object being built to "fix in place" the result
evaluate f a
evaluate f 'a
evaluate delta = f 'a - f a
read f a + f b + f c from the result
evaluate f a + f b + f c + delta
Notice this algorithm doesn't require the first algorithm to memoize any intermediate computation
David Eppstein and other American algorithmicians are typical representatives of this line of work