Graph Theory37 sections · 1633 units
Open in Course

Lessons - Flow Decomposition

(Paths from flow)

Max flow tells you how many edge-disjoint paths exist, but extracting them requires flow decomposition. Trace paths greedily by following flow. This is a standard post-processing step. This technique works for any flow network. If you need to list the actual paths, not count them, decomposition is necessary.

Many problems ask for both. Flow decomposition takes O(mf)O(m \cdot f) time where ff is the flow value, since each path is traced in O(m)O(m) time. For small flow values, this is fast.