科研之友
微信
新浪微博
Facebook
分享链接
摘要
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 (2) n (3) 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 (2) m) time by introducing a new sophisticated data structure. We describe an algorithm that runs in O(k (3) n (3)+kn (2) m) time without using sophisticated data structures. In addition, we present an application of the algorithm to find a shortest dijoin in O(n (2) m) time, which matches the current best bound.
- 出版日期2010-4
