2002/12/30 by Harold N. Gabow · 1 citation
Computer Science · Mathematics · #Complexity and Algorithms in Graphs #Advanced Graph Theory Research #Optimization and Search Problems #Minimum-cost flow problem #Orientation (vector space) #Submodular set function #Scaling #Flow network #Combinatorics #Mathematics #Upper and lower bounds #Vertex (graph theory) #Flow (mathematics) #Enhanced Data Rates for GSM Evolution #Approximation algorithm #Algorithm #Computer science #Graph #Geometry #Artificial intelligence
paper · doi:10.1109/sfcs.1993.366842
openalex publication_date 2002/12/30 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/29
The submodular flow problem includes such problems as minimum-cost network flow, dijoin, edge-connectivity orientation and others. We present a cost-scaling algorithm for submodular flow problems. The algorithm applies to these problems in general; we also examine its efficiency for the dijoin and edge-connectivity orientation problems. A minimum-cost dijoin is found in time O(minm/sup 1/2/, n/sup 2/3/nmlog(nN)), where n, m and N denote the number of vertices, number of edges and largest magnitude of an integral edge cost. The previous best-known bound is O(n/sup 2/m) if fast matrix multiplication is not used. A k-edge-connected orientation is found in time O(kn/sup 2/(/spl radic/(kn)+k/sup 2/log(n/k))). A minimum-cost k-edge-connected orientation is found on the above time bound for dijoins when k=O(1) (and a more complicated bound for general k). The scaling algorithm uses a transformation that eliminates vertex weights in edge-capacitated graphs. It also incorporates a scheme to limit the growth in the size of intermediate solutions, using a dual minimum-cost network flow problem.>