Previous | Next --- Slide 25 of 81
Back to Lecture Thumbnails
assignment7

The paper is here, in the paper, there are also some discussions about how to combine top-down and bottom-up

pslui88

This graph is illustrating that for each step in BFS, the frontier grows very quickly up to a certain point, then drops very quickly because there are fewer and fewer unvisited nodes left. Furthermore, most edge visits are wasteful because they are more likely to lead to a node that has already been visited by one of the other nodes also adjacent to it. This is why Ligra's heuristic is so helpful -- it can dynamically tell when to change strategies based on how much of the graph has been processed so far.

Please log in to leave a comment.