Concepedia

Cut-flow Duality

Cut-Flow Duality is a theoretical principle in network flow algorithms that establishes the equivalence between the maximum value of a flow in a network and the minimum capacity of a cut separating the source from the sink.

38

Publications

2.4K

Citations

82

Authors

54

Institutions

Publications per year

2017–2026

4

Parents

Publications

38

Polynomial Time Algorithms for Multicast Network Code Construction

Sidharth Jaggi, Peter Sanders, Philip A. Chou et al. · IEEE Transactions on Information Theory · 2005 · 965 citations · Full text

, , +17

Totally Balanced Games and Games of Flow

Ehud Kalai, Eitan Zemel · Mathematics of Operations Research · 1982 · 209 citations

, , +15

On Odd Cuts and Plane Multicommodity Flows

Paul Seymour · Proceedings of the London Mathematical Society · 1981 · 144 citations

, , +7

An Improved Parameterized Algorithm for the Minimum Node Multiway Cut Problem

Jianer Chen, Yang Liu, Songjian Lu · Algorithmica · 2007 · 131 citations

, , +10

Fast Approximation Algorithms for Cut-Based Problems in Undirected Graphs

Aleksander Mądry · 2010 · 80 citations

, , +11

1–5 of 38

Authors

82

  1. EZ
    Eitan Zemel

    Northwestern University, United States

    2 publications · 229 citations

    2

    h-index

  2. EK
    Ehud Kalai

    Northwestern University, United States

    2 publications · 229 citations

    2

    h-index

  3. AM
    Aleksander Mądry

    Massachusetts Institute of Technology, United States

    2 publications · 94 citations

    2

    h-index

  4. PS
    Paul Seymour

    Princeton University, United States

    2 publications · 168 citations

    2

    h-index

  5. AB
    Allon Bloch

    Ariel University, Israel

    1 publications · 21 citations

    1

    h-index

1–5 of 82

Institutions

54

  1. Massachusetts Institute of Technology

    Cambridge, United States

    4 h-index

    4 publications

    209 citations

  2. Karlsruhe Institute of Technology

    Karlsruhe, Germany

    3 h-index

    5 publications

    1.1K citations

  3. University of California, Berkeley

    Berkeley, United States

    2 h-index

    2 publications

    64 citations

  4. University of California San Diego

    San Diego, United States

    2 h-index

    4 publications

    84 citations

  5. UNSW Sydney

    Sydney, Australia

    1 h-index

    2 publications

    20 citations

  6. Simons Center for Geometry and Physics

    Stony Brook, United States

    1 h-index

    1 publications

    16 citations

  7. Microsoft (United States)

    Redmond, United States

    1 h-index

    1 publications

    965 citations

  8. Direction des Services de la Navigation Aérienne

    Athis-Mons, France

    1 h-index

    1 publications

    15 citations

1–8 of 54

Venues

  1. Algorithmica

    3 publications · 187 citations

    3

    h-index

  2. arXiv (Cornell University)

    Repository · 3 publications · 41 citations

    3

    h-index

  3. Mathematics of Operations Research

    2 publications · 231 citations

    2

    h-index

  4. Discrete Applied Mathematics

    2 publications · 28 citations

    2

    h-index

  5. Discrete Mathematics

    2 publications · 34 citations

    2

    h-index

1–5