Name
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. |
Year | DOI | Venue |
|---|---|---|
2015 | 10.1007/978-3-662-48350-3_10 | ALGORITHMS - ESA 2015 |
Field | DocType | Volume |
Graph,Combinatorics,Computer science,Parallel algorithm,Algorithm,Implementation,Theoretical computer science,Maximum flow problem | Journal | 9294 |
ISSN | Citations | PageRank |
0302-9743 | 1 | 0.35 |
References | Authors | |
18 | 3 | |
Name | Order | Citations | PageRank |
|---|---|---|---|
| Niklas Baumstark | 1 | 1 | 0.35 |
| Guy E. Blelloch | 2 | 2927 | 207.30 |
| Julian Shun | 3 | 593 | 32.57 |