Fast cycle canceling algorithms for minimum cost submodular flow
type: Item
instance of: scholarly article
title: Fast cycle canceling algorithms for minimum cost submodular flow
zbMATH Open document ID: 1099.90052
author: Satoru Iwata
author: Maiko Shigeno
author: S. Thomas McCormick
published in: Combinatorica
publication date: 2004-10-19T00:00:00Z
review text: The authors present two new algorithms for the submodular flow problem on a directed graph, introduced by \textit{J. Edmonds} and \textit{R. Giles} [Ann. Discrete Math. 1, 185--204 (1977; Zbl 0373.05040)]. The key idea for the first algorithm is to use an assignment subproblem for determining a most negative family of node-disjoint cycles in an auxiliary graph. These cycles are repeatedly cancelled by the algorithm. The main idea of the second algorithm is to cancel cycles in the subgraph of negative reduced cost arcs until it is acyclic. At this point a change to dual variables that remove at least one node from participating in next negative cycles is made. It is shown that proposed algorithms can be modified so that the running times of both are \(O(n^6h\log n)\), where \(n\) is the number of nodes and \(h\) is the time for computing an exchange capacity. Finally, the authors consider an extension of the algorithms to submodular flows with separable convex objectives. This paper, despite some unexplained notations, is well worth reading by anyone interested in flow problems on directed graphs.
Mathematics Subject Classification ID: 90C27
Mathematics Subject Classification ID: 90C35
Mathematics Subject Classification ID: 90B10
Mathematics Subject Classification ID: 90C25
zbMATH DE Number: 2108641
zbMATH Keywords: submodular flow problem
zbMATH Keywords: directed graps
zbMATH Keywords: algorithms
zbMATH Keywords: Zbl 0373.05040
reviewed by: Ivan Martinec
MaRDI profile type: Publication
full work available at URL: s00493-003-0030-3
OpenAlex ID: W1986273263
DOI: 10.1007/S00493-003-0030-3
Recommended article: Q4250177
Recommended article: A Primal-Dual Algorithm for Submodular Flows
Recommended article: Q3220319
Recommended article: A submodular network simplex method
Recommended article: A fast cost scaling algorithm for submodular flow
Recommended article: Submodular flow problem with a nonseparable cost function
Recommended article: A Push/Relabel framework for submodular flows and its definement for 0-1 submodular flows
Recommended article: An algorithm for minimum cost arc-connectivity orientations
Recommended article: A polynomial cycle canceling algorithm for submodular flows
Recommended article: Q4263717
description: scientific article; zbMATH DE number 2108641