Supposing that you have the complete graph G, of the distances between every pair of nodes. Computing the minimum spanning tree algortihm, MST(G), you get a graph with a single path between any pair of nodes. After that, you remove the edges of MST(G) from the original complete graph G, obtaining G' = G - MST(G). Then, compute the minimum spanning tree in G'. Note that all edges in MST(G') are different from the edges in MST(G), because you G' does not contain MST(G) edges. Through the union of the edges (MST(G) U MST(G')) you get a graph with at least two edge-independent paths between any pair of nodes. The name of this algorithm is RedundantMST and one example of its application is to generate energy-efficient fault-tolerant topologies for WSNs . For further information please refer to the following paper, specificaly section 3.3, it includes the pseudo-code for RedundantMST algorithm. Hope it helps.
Best regards,
Conference Paper Fault Tolerance in Strongly Minimum Energy Topology with MLD...
You can use Suurballe's algorithm (http://en.wikipedia.org/wiki/Suurballe%27s_algorithm) to find two vertex disjoint shortest path between the source and sink. Then use one of the paths as primary and use the other as secondary. Whenever a primary path fails, there will be a disjoint backup path that can take over.
- Badges
- Science topic