Visualizing, Finding and Packing Dijoins

We consider the problem of strengthening a network to become strongly connected. That is, so that between any pair of nodes, there is a directed path in each direction. We are allowed to achieve this by turning some of the network links (each at a different cost) into two-way arcs, or equivalently, replacing these arcs by a dijoin. Despite its fundamental nature, this problem is not a standard modelling tool for the combinatorial optimizer in the same way that shortest paths, negative cycle detection, matchings and network flows are. Widespread adoption of these other problems stems from the fact that there are fast algorithms that are implemented and taught using only simple concepts such as dynamic programming, greedy algorithms, shrinking, and tree growing. One of our present objectives is to present a simple version of Frank's algorithm that matches the fastest known running time (O(nsup 2 m) due to Gabow) but uses only standard techniques such as arborescence growing and negative cycle detection.