Concepedia

Push-relabel Algorithms

Push-Relabel Algorithms is a class of efficient network flow algorithms that compute maximum flow by maintaining a preflow and iteratively pushing excess flow toward the sink while relabeling vertices to ensure progress, differing from augmenting-path methods by decoupling the operations of flow advancement and path discovery.

41

Publications

6.6K

Citations

75

Authors

44

Institutions

Publications per year

2017–2026

2

Variants

Push-relabel Algorithm

Parents

Publications

41

An experimental comparison of min-cut/max- flow algorithms for energy minimization in vision

Yuri Boykov, Vladimir Kolmogorov · IEEE Transactions on Pattern Analysis and Machine Intelligence · 2004 · 4.6K citations

, , +11

On Implementing the Push—Relabel Method for the Maximum Flow Problem

Boris V. Cherkassky, Andrew V. Goldberg · Algorithmica · 1997 · 372 citations

, , +9

CUDA cuts: Fast graph cuts on the GPU

Vibhav Vineet, P. J. Narayanan · 2008 · 248 citations

, , +17

Performance Analysis and Best Implementations of Old and New Algorithms for the Open-Pit Mining Problem

Dorit S. Hochbaum · Operations Research · 2000 · 175 citations

, , +15

A Scalable graph-cut algorithm for N-D grids

Andrew Delong, Yuri Boykov · 2008 · 108 citations

, , +15

1–5 of 41

Authors

75

  1. AV
    Andrew V. Goldberg

    Stanford University, United States

    7 publications · 576 citations

    7

    h-index

  2. SI
    Satoru Iwata

    The University of Tokyo, Japan

    3 publications · 225 citations

    3

    h-index

  3. BH
    Bo Hong

    Georgia Institute of Technology, United States

    3 publications · 72 citations

    3

    h-index

  4. DS
    Dorit S. Hochbaum

    University of California, Berkeley, United States

    3 publications · 284 citations

    3

    h-index

  5. SP
    Serge Plotkin

    Stanford University, United States

    2 publications · 81 citations

    2

    h-index

1–5 of 75

Institutions

44

  1. Stanford University

    Stanford, United States

    4 h-index

    8 publications

    628 citations

  2. University of California, Berkeley

    Berkeley, United States

    3 h-index

    5 publications

    485 citations

  3. University of British Columbia

    Vancouver, Canada

    2 h-index

    2 publications

    65 citations

  4. Purdue University West Lafayette

    West Lafayette, United States

    2 h-index

    2 publications

    26 citations

  5. University of Bergen

    Bergen, Norway

    2 h-index

    2 publications

    35 citations

  6. Western University

    London, Canada

    2 h-index

    3 publications

    4.8K citations

  7. Central Economics and Mathematics Institute

    Moscow, Russia

    2 h-index

    2 publications

    428 citations

  8. Simula Research Laboratory

    Oslo, Norway

    2 h-index

    2 publications

    35 citations

1–8 of 44

Venues

  1. Operations Research

    3 publications · 323 citations

    3

    h-index

  2. 2

    h-index

  3. ACM Journal of Experimental Algorithmics

    JEA · 2 publications · 66 citations

    2

    h-index

  4. Journal of Algorithms

    2 publications · 52 citations

    2

    h-index

  5. Algorithmica

    1 publications · 372 citations

    1

    h-index

1–5