A distributed mincut/maxflow algorithm combining path augmentation and push-relabel

DOI10.1007/S11263-012-0571-2MaRDI QIDQ2254255zbMATH OpenOpenAlexFDO

Authors Alexander Shekhovtsov, Václav Hlaváč

Publication date 4 February 2015

Published in International Journal of Computer Vision (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1109.1146

zbMATH Keywords

augmenting pathdistributed algorithmlarge scalemaximum flowminimum cutparallel algorithmpush-relable

Mathematics Subject Classification ID

Machine vision and scene understanding (68T45) Distributed algorithms (68W15) Combinatorial optimization (90C27)

Abstract: We develop a novel distributed algorithm for the minimum cut problem. We primarily aim at solving large sparse problems. Assuming vertices of the graph are partitioned into several regions, the algorithm performs path augmentations inside the regions and updates of the push-relabel style between the regions. The interaction between regions is considered expensive (regions are loaded into the memory one-by-one or located on separate machines in a network). The algorithm works in sweeps - passes over all regions. Let $B$ be the set of vertices incident to inter-region edges of the graph. We present a sequential and parallel versions of the algorithm which terminate in at most $2|B{|}^2+1$ sweeps. The competing algorithm by Delong and Boykov uses push-relabel updates inside regions. In the case of a fixed partition we prove that this algorithm has a tight $O(n^2)$ bound on the number of sweeps, where $n$ is the number of vertices. We tested sequential versions of the algorithms on instances of maxflow problems in computer vision. Experimentally, the number of sweeps required by the new algorithm is much lower than for the Delong and Boykov's variant. Large problems (up to $10^8$ vertices and $6cdot10^8$ edges) are solved using under 1GB of memory in about 10 sweeps.

Recommendations

• scientific article; zbMATH DE number 1849127
• A multigrid algorithm for maxflow and min-cut problems with applications to multiphase image segmentation
• Reduced graphs for min-cut/max-flow approaches in image segmentation
• Maximum flows by incremental breadth-first search
• Practical minimum cut algorithms

Cites work

• A new approach to the maximum-flow problem
• Beyond the flow decomposition barrier
• scientific article; zbMATH DE number 1849127 (Why is no real title available?)
• On implementing the push-relabel method for the maximum flow problem
• Processor-efficient implementation of a maximum flow algorithm
• The Partial Augment–Relabel Algorithm for the Maximum Flow Problem

Cited in

(4)

• A multigrid algorithm for maxflow and min-cut problems with applications to multiphase image segmentation
• Maximum flows by incremental breadth-first search
• TBGMax: leveraging two-boundary graph pattern for lossless maximum-flow acceleration
• Composability and controllability of structural linear time-invariant systems: distributed verification

Describes a project that uses

Uses Software

• MAXFLOW

This page was built for publication: A distributed mincut/maxflow algorithm combining path augmentation and push-relabel

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2254255)