A Note on Duality in Network Flows.
Abstract
Two concepts of duality are introduced in the network flow theory: The topological notion of dual graph which is associated to planar networks, the analytical notion of duality between flows and potentials associated to the same network. By combining these two notions, it is known that a max-flow problem in a planar network is equivalent to a shortest route problem in the topological dual graph. This correspondence is described with precision here. (Author)
Document Details
- Document Type
- Technical Report
- Publication Date
- Nov 01, 1970
- Accession Number
- AD0716582
Entities
People
- Michel F. Sakarovitch
Organizations
- University of California, Berkeley