Re: discuss dancing links

chenyan wrote:
> In what situation is Knuth's "dancing links" technique be powerful?
> I apply it to Maximal Independent Set problem, but it runs slower
than
> adjacency list representation. I want to know is there something
wrong with
> my implementation or the technique is not suitable for this problem.
Thanks.

The point of the technique is that you can back up to previous
states without having to make independent copies of all the
intermediate states. In your program with the adjacency list
representation, are you able to easily (i.e. without searching
through the adjacency lists) able to back up to previous states
of your graph without making independent copies of each successive
graph? If so, then there is no reason to go to the doubly-linked
list method described in Knuth's "dancing links" paper. In such
a case, the singly-linked adjacency list method is likely to be
faster because the doubly-linked list has twice as many links to
set and reset.

.