An Algorithm for Minimum Cost Arc-Connectivity Orientations |
| |
Authors: | Satoru Iwata Yusuke Kobayashi |
| |
Affiliation: | 1. Research Institute for Mathematical Sciences, Kyoto University, Kyoto, 606-8502, Japan 2. Graduate School of Information Science and Technology, University of Tokyo, Bunkyo-ku, Tokyo, 113-8656, Japan
|
| |
Abstract: | 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. |
| |
Keywords: | |
本文献已被 SpringerLink 等数据库收录! |
|