Questions tagged [transitive-reduction]

The tag has no usage guidance.

Filter by
Sorted by
Tagged with
8
votes
2answers
4k views

Reducing redundant edges from a dependency graph

I have a DAG of dependencies that contains lots of redundant edges (see example below). I want a "quick" algorithm (ie. can handle a graph with several thousands of nodes/edges) that finds a minimal ...
7
votes
1answer
757 views

Approximating transitive reduction of a transitive closure of a dag

Let's suppose a transitive closure $G^+$ of a dag $G$ is given and we want to compute an approximation of the transitive reduction $G^-$ such that the full transitive reduction is a subgraph of the ...