0
$\begingroup$

Is there a name for the relationship between two DAGs A,B where B is one of the transitive reductions of the transitive closure C of A?

For example the connectivity of nodes in both graphs would still be the same.

For example, we can connect all nodes in A to their minimal elements (smallest subsets) in A and remove all other edges, leading to B.

Improve this question
$\endgroup$
4
  • 1
    $\begingroup$ Some authors require transitive reductions to be a subgraph of the original graph (an edge in the reduction must be an edge in the original graph), and some don't - a transitive reduction just has to be a graph on the same vertex set whose transitive closure is the same. $\endgroup$
    – Joppy
    Nov 4, 2020 at 23:40
  • $\begingroup$ That is also what came to my mind but then I read the Wikipedia article of transitive reduction, where it says "The transitive reduction of a finite directed acyclic graph (a directed graph without directed cycles) is unique and is a subgraph of the given graph." Note that in my concept there might be edges in B that are not in the original graph A. $\endgroup$
    – Radio Controlled
    Nov 5, 2020 at 8:31
  • 1
    $\begingroup$ I was meaning that there seem to be two different notions kicking around which are in use, so perhaps just say "a transitive closure of A" rather than "the transitive closure of A", and the first time you introduce the concept make sure it's clear which notion you mean $\endgroup$
    – Joppy
    Nov 5, 2020 at 8:33
  • $\begingroup$ @Joppy, I think your point is worth an answer, in particular if you could find one example for each view ("some authors do, some don't"). $\endgroup$
    – Radio Controlled
    Nov 5, 2020 at 8:33

0

Reset to default

Your Answer

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

Browse other questions tagged or ask your own question.