2
$\begingroup$

In a recent algorithms course we had to form a condensation graph and compute its reflexive-transitive closure to get a partial order. But it was never really explained why we would want to do that in a graph. I understand the gist of a condensation graph in that it highlights the strongly connected components, but what does the partial order give us that the original graph did not?

The algorithm implemented went like this:

  1. Find strongly connected components (I used Tarjan)

  2. Create condensation graph for the SCCs

  3. Form reflexive-transitive closure of adjacency matrix (I used Warshall)

Doing that forms the partial order, but.... what advantage does finding the partial order give us?

$\endgroup$
4
$\begingroup$

One possible use: It lets you answer the question "is vertex $y$ reachable from vertex $x$?" in $O(1)$ time.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.