other · Computer Science Publication Server (University of Cologne) · 2010

Preprocessing Maximum Flow Algorithms

Liers, Frauke, Pardella, Gregor

Cited by 0Open access

Abstract

Maximum-flow problems occur in a wide range of applications. Although already well-studied, they are still an area of active research. The fastest available implementations for determining maximum flows in graphs are either based on augmenting-path or on push-relabel algorithms. In this work, we present two ingredients that, appropriately used, can considerably speed up these methods. On the one hand, we present flow-conserving conditions under which subgraphs can be contracted to a single node. These rules are in the same spirit as presented by Padberg and Rinaldi (Math. Programming (47), 1990) for the minimum cut problem in graphs. On the other hand, we propose a two-step max-flow algorithm for solving the problem on instances coming from physics and computer vision. In the two-step algorithm flow is first sent along augmenting paths of restricted lengths only. Starting from this flow, the problem is then solved to optimality using some known max-flow methods. By extensive experiments on random instances and on instances coming from applications in theoretical physics and in computer vision, we show that a suitable combination of the proposed techniques speeds up traditionally used methods.

Cite this paper

APA 7

Liers, F., & Pardella, G. (2010). Preprocessing Maximum Flow Algorithms. Computer Science Publication Server (University of Cologne).

MLA 9

Liers, Frauke, and Gregor Pardella. “Preprocessing Maximum Flow Algorithms.” Computer Science Publication Server (University of Cologne), 2010.

Chicago

Liers, Frauke, and Gregor Pardella. 2010. “Preprocessing Maximum Flow Algorithms.” Computer Science Publication Server (University of Cologne).

Harvard

Liers, F. and Pardella, G. (2010) ‘Preprocessing Maximum Flow Algorithms’, Computer Science Publication Server (University of Cologne).

BibTeX

@misc{liers2010preprocessing,
  title = {{Preprocessing Maximum Flow Algorithms}},
  author = {Liers, Frauke and Pardella, Gregor},
  journal = {Computer Science Publication Server (University of Cologne)},
  year = {2010}
}

Made from the index record. Check names, capitalisation and page numbers against the paper. Need another style? AI for Research has over 10,000.