1.4.9 Network Flow

Problem Input | Problem Output 


INPUT                    OUTPUT

Input Description: A graph G , where each edge (i,j) has a capacity c_{i,j} . A source node and sink node t .

Problem: What is the maximum flow you can route from to t while respecting the capacity of each edge.

Implementations

  • Goldberg's Network Optimization Codes (C) (rating 10)
  • DIMACS Implementation Challenges (FORTRAN) (rating 8)
  • LEDA - A Library of Efficient Data Types and Algorithms (C++) (rating 5)
  • Moret and Shapiro's Algorithms P to NP (Pascal) (rating 4)
  • Discrete Optimization Methods (Pascal) (rating 4)
  • Combinatorica (Mathematica) (rating 3)
  • GraphEd -- Graph Editor and Layout Program (C) (rating 3)
  • Nijenhuis and Wilf: Combinatorial Algorithms (FORTRAN) (rating 3)

    Related Problems

  • Edge and Vertex Connectivity
  • Graph Partition
  • Linear Programming
  • Matching
  • Shortest Path

    Go to the corresponding chapter in the book
    About the Book
    Send us Mail
    Go to Main Page

    This page last modified on Tue Jun 03, 1997 .