An Algorithm for Minimum Cost Arc-Connectivity Orientations

Given a 2k-edge-connected undirected graph, we consider to find a minimum cost orientation that yields a k-arc-connected directed graph. This minimum cost k-arc-connected orientation problem is a special case of the submodular flow problem. Frank (1982) devised a combinatorial algorithm that solves the problem in O(k ² n ³ m) time, where n and m are the numbers of vertices and edges, respectively. Gabow (1995) improved Frank’s algorithm to run in O(kn ² m) time by introducing a new sophisticated data structure. We describe an algorithm that runs in O(k ³ n ³+kn ² m) time without using sophisticated data structures. In addition, we present an application of the algorithm to find a shortest dijoin in O(n ² m) time, which matches the current best bound.