Efficient implementation of a synchronous parallel push-relabel algorithm

DOI10.1007/978-3-662-48350-3_10MaRDI QIDQ3452773zbMATH OpenOpenAlexFDO

Authors Niklas Baumstark, Guy E. Blelloch, Julian Shun

Publication date 19 November 2015

Published in Algorithms - ESA 2015 (Search for Journal in Brave)

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

Mathematics Subject Classification ID

Graph theory (including graph drawing) in computer science (68R10) Parallel algorithms in computer science (68W10)

Abstract: Motivated by the observation that FIFO-based push-relabel algorithms are able to outperform highest label-based variants on modern, large maximum flow problem instances, we introduce an efficient implementation of the algorithm that uses coarse-grained parallelism to avoid the problems of existing parallel approaches. We demonstrate good relative and absolute speedups of our algorithm on a set of large graph instances taken from real-world applications. On a modern 40-core machine, our parallel implementation outperforms existing sequential implementations by up to a factor of 12 and other parallel implementations by factors of up to 3.

Recommendations

• scientific article; zbMATH DE number 515925
• The Partial Augment–Relabel Algorithm for the Maximum Flow Problem
• On implementing the push-relabel method for the maximum flow problem
• On implementing push-relabel method for the maximum flow problem
• Processor-efficient implementation of a maximum flow algorithm

Cites work

• scientific article; zbMATH DE number 3174052 (Why is no real title available?)
• scientific article; zbMATH DE number 487935 (Why is no real title available?)
• A computational study of the pseudoflow and push-relabel algorithms for the maximum flow problem
• A new approach to the maximum-flow problem
• An O(n2log n) parallel max-flow algorithm
• Efficient implementation of a synchronous parallel push-relabel algorithm
• Engineering multilevel graph partitioning algorithms
• Graph Partitioning and Graph Clustering
• Maximum flows by incremental breadth-first search
• On implementing the push-relabel method for the maximum flow problem
• The Pseudoflow Algorithm: A New Algorithm for the Maximum-Flow Problem

Cited in

(4)

• Algorithm 1002: Graph coloring based parallel push-relabel algorithm for the maximum flow problem
• Scalable high-quality hypergraph partitioning
• scientific article; zbMATH DE number 515925 (Why is no real title available?)
• Efficient implementation of a synchronous parallel push-relabel algorithm

Describes a project that uses

Uses Software

• CMU Benchmarks
• DIMACS
• KaFFPa

This page was built for publication: Efficient implementation of a synchronous parallel push-relabel algorithm

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