Algorithm for Finding Redundant Edges in a Graph or Tree

algorithm language-agnostic tree graph-theory
Ryan Fox picture Ryan Fox · Feb 4, 2009 · Viewed 9.9k times · Source

Is there an established algorithm for finding redundant edges in a graph?

For example, I'd like to find that a->d and a->e are redundant, and then get rid of them, like this:

alt text => alt text

Edit: Strilanc was nice enough to read my mind for me. "Redundant" was too strong of a word, since in the example above, neither a->b or a->c is considered redundant, but a->d is.

Answer

Craig Gidney picture Craig Gidney · Feb 4, 2009

You want to compute the smallest graph which maintains vertex reachability.

This is called the transitive reduction of a graph. The wikipedia article should get you started down the right road.

Related questions

How to efficiently build a tree from a flat structure?

I have a bunch of objects in a flat structure. These objects have an ID and a ParentID property so they can be arranged in trees. They are in no particular order. Each ParentID property does not necessarily matches with …

Read More
reconstructing a tree from its preorder and postorder lists

Consider the situation where you have two lists of nodes of which all you know is that one is a representation of a preorder traversal of some tree and the other a representation of a postorder traversal of the same …

Read More
Hash table vs Balanced binary tree

What factors should I take into account when I need to choose between a hash table or a balanced binary tree in order to implement a set or an associative array?

Read More