Suppose that we wish to maintain the transitive closure of a directed graph G = (V, E) as we insert edges into E. That is, after each edge has been inserted, we want to update the transitive closure of the edges inserted so far. Assume that the graph G has no edges initially and that the transitive closure is to be represented as a Boolean matrix.
a. Show how the transitive closure G* = (V, E*) of a graph G = (V, E) can be updated in O (V2) time when a new edge is added to G.

  • CreatedJuly 14, 2010
  • Files Included
Post your question