Routing without ordering
Bernadette Charron-Bost, Antoine Gaillard, Jennifer Lundelius Welch, Josef Widder · 2009
We analyze the correctness and the complexity of two well-known routing algorithms, introduced by Gafni and Bertsekas (1981): By reversing the directions of some edges, these algorithms transform an arbitrary directed acyclic input graph into an output graph with at least one route from each node to a special destination node (while maintaining acyclicity). The resulting graph can thus be used to route messages in a loop-free manner.