Re: discuss dancing links

"gcrhoads@xxxxxxxxx" <gcrhoads@xxxxxxxxx> wrote in message news:
>
> 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.

I think the advantage of this technique is we don't have to check
whether a node is valid or not. When choosing a node we can delete all
the adjacent nodes so that we can sure all the remaining nodes are
valid. While in adjacency lists deleting a node and then add it when
backtracing can be time-consuming. So in my program, I delete adjacent
nodes in dancing links while checking whether a node is valid in
adjacency list representation. I don't know whether saving the
checking time compensates for the waste of maintaining the
doubly-linked list. Can it be efficient in some graphs with special
structure?
.

Relevant Pages

  • Re: discuss dancing links
    ... >> through the adjacency lists) able to back up to previous states ... > I think the advantage of this technique is we don't have to check ... You can quickly splice these edges ... out via "dancing links" and quickly update the degree of the node. ...
    (comp.theory)
  • Re: Which dataStructure should I use?
    ... >> be represented as a graph. ... An adjacency lists have a linked list for each vertex. ... you would use adjacency matrices for dense graphs and ... adjacency lists for sparse graphs. ...
    (comp.programming)
  • Re: Neighbors of a Vertex
    ... I have a question about finding neighbors of a given vertex in a ... Suppose there are n vertices in the graph, for one vertex P, how ... can I find all its neighbors, which are away AT MOST r units from ... If you preprocess the graph and sort the adjacency lists then you can achieve Owhere k is the number of vertices output. ...
    (comp.programming)