Algorithm for Finding Redundant Edges in a Graph or Tree

Answer 1

A sub-graph of a given graph which contains no "redundant edges" is called a 'spanning tree' of that graph. For any given graph, multiple spanning trees are possible.

So, in order to get rid of redundant edges, all you need to do is find any one spanning tree of your graph. You can use any depth-first-search or breadth-first-search algorithm and continue searching till you have visited every vertex in the graph.

Answer 2

Check this: Minimum Spanning Tree

Answer 3

I think the easiest way to do that, actually imagine how it would look in the real work, imagine if you have joints, Like

(A->B)(B->C)(A->C), imagine if distance between near graphs is equals 1, so

(A->B) = 1, (B->C) = 1, (A->C) = 2.

So you can remove joint (A->C).

In other words, minimize.

This is just my idea how I would think about it at start. There are various articles and sources on the net, you can look at them and go deeper.

Resources, that Will help you:

Algorithm for Removing Redundant Edges in the Dual Graph of a Non-Binary CSP

Graph Data Structure and Basic Graph Algorithms

Google Books, On finding minimal two connected Subgraphs

Graph Reduction

Redundant trees for preplanned recovery in arbitraryvertex-redundant or edge-redundant graphs

Answer 4

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.