Universität zu Köln

Liers, Frauke and Pardella, Gregor (2011). Simplifying maximum flow computations: The effect of shrinking and good initial flows. Discret Appl. Math., 159 (17). S. 2187 - 2204. AMSTERDAM: ELSEVIER SCIENCE BV. ISSN 0166-218X

Full text not available from this repository.

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 theoretical side, we present flow-conserving conditions under which subgraphs can be contracted to a single vertex. These rules are in the same spirit as presented by Padberg and Rinaldi (1990) [12] for the minimum cut problem in graphs. These rules allow the reduction of known worst-case instances for different maximum flow algorithms to equivalent trivial instances. On the practical side, 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 instances coming from applications in theoretical physics and computer vision, we show that a suitable combination of the proposed techniques speeds up traditionally used methods. (C) 2011 Elsevier B.V. All rights reserved.

Item Type:	Journal Article
Creators:	Creators Email ORCID ORCID Put Code Liers, Frauke UNSPECIFIED UNSPECIFIED UNSPECIFIED Pardella, Gregor UNSPECIFIED UNSPECIFIED UNSPECIFIED
URN:	urn:nbn:de:hbz:38-486983
DOI:	10.1016/j.dam.2011.06.030
Journal or Publication Title:	Discret Appl. Math.
Volume:	159
Number:	17
Page Range:	S. 2187 - 2204
Date:	2011
Publisher:	ELSEVIER SCIENCE BV
Place of Publication:	AMSTERDAM
ISSN:	0166-218X
Language:	English
Faculty:	Faculty of Mathematics and Natural Sciences
Divisions:	Faculty of Mathematics and Natural Sciences > Department of Mathematics and Computer Science > Institute of Computer Science
Subjects:	no entry
Uncontrolled Keywords:	Keywords Language ALGORITHMS; NETWORK Multiple languages Mathematics, Applied Multiple languages
Refereed:	Yes
URI:	http://kups.ub.uni-koeln.de/id/eprint/48698