# Transitive Closure (Strongly Connected Components)

Jump to navigation
Jump to search

## Description

In this problem, we also want to compute the transitive closure of a graph. (Perhaps this should be a separate problem?)

## Related Problems

Related: Strongly Connected Components, Maximum Strongly Connected Component, Strong Connectivity (dynamic), 2 Strong Components (dynamic), Connected Subgraph

## Parameters

$V$: number of vertices

$E$: number of edges

## Table of Algorithms

Name | Year | Time | Space | Approximation Factor | Model | Reference |
---|---|---|---|---|---|---|

Paul Purdom | 1970 | $O(V^{2}+VE)$ | $O(V^{2})$ | Exact | Deterministic | Time & Space |