> However, that would probably not be worth a lot because you
> want to memoize small things that are expensive to compute,
> not large things that are easy to compute. Just checking
> that G had not changed would cost as much as computing
> the adjacency matrix, I think.
The maximum clique (or even its cardinality) might be a better example.
As for checking whether G had changed, there are three approaches I can
see:
1) Make G immutable, so the question never comes up.
2) Make all modifications to G go through a well-defined interface, so
that changes can be detected and cached results either updated or
invalidated.
3) Checking each time.
-s