Given an equivalence relation over the set of vertices of a graph,
I could not understand how one builds the "qoutient graph" in linear time.
For example, in the strongly connectedness relation, we somehow built the super-graph,
I don't understand how to do that without set-operations which take O(E*logV).
Date: 29 Jan 2015 14:52
Number of posts: 4
RSS: New posts
We showed how to do this is class - you use DFS twice to build the super-graph. You can see it here as well http://en.wikipedia.org/wiki/Strongly_connected_component
It's obviously possible to do it in other ways as well, but that is pretty much the point of this course - to show algorithms that do things efficiently.
I understand how to find the strongly-connected components, what I don't understand is how to build the super-graph afterwords in linear time.
All we do is contract each CC to a single vertex, and we immediately get the super-graph.
You can do this in several ways. A simple, though probably quite "ugly" one is to add a new vertex for each CC, with "special" edges to and from each vertex that is in it. You added |V| vertices and |V| edges, so the running times on this graph are going to be asymptotically the same.
You are probably concerned that there are now parallel edges in the SCC graph. That's okay, we don't mind that (notice that we hardly ever actually REQUIRED that the graphs are simple, it's just usually easier visualize them and to prove things on simple graphs.)