Questions tagged [transitive-reduction]

The tag has no usage guidance.

Filter by
Sorted by
Tagged with
1 vote
0 answers

Upper bound on the number of maximal paths in rooted intransitive DAGs

Let $D(V, A)$ be a DAG. Definition 0: We name a path between two nodes $i$ and $j$ as an $i$-$j$-path. Definition 1: Let $p$ be a path, we call $|p|$ the path length, representing the number of arcs ...
Matheus Diógenes Andrade's user avatar
8 votes
2 answers

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 ...
Iftah's user avatar
  • 189
7 votes
1 answer

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 ...
Alexandru's user avatar
  • 696