Title :
A topological max-flow-min-cut theorem
Author :
Ghrist, Robert ; Krishnan, Sridhar
Author_Institution :
Depts. of Math., Univ. of Pennsylvania, Philadelphia, PA, USA
Abstract :
This note surveys a novel algebraic-topological version of the max-flow-min-cut (MFMC) theorem for directed networks with capacity constraints. Novel features include the encoding of capacity constraints as a sheaf of semimodules over the network and a realization of flow and cut values as a directed homology taking values in the sheaf. We survey the theorem and give applications to (1) multicommodity flows, (2) multi-source/multi-target flows, and (3) boolean-lattice-valued flows.
Keywords :
algebra; network theory (graphs); topology; Boolean-lattice-valued flows; MFMC; algebraic-topological version; capacity constraints; directed networks; max-flow-min-cut theorem; multicommodity flows; multisource-multitarget flows; network semimodules; topological max-flow-min-cut theorem; Educational institutions; Encoding; Lattices; Network topology; Optimization; Topology; Vectors; network flow; optimization; sheaves; topology;
Conference_Titel :
Global Conference on Signal and Information Processing (GlobalSIP), 2013 IEEE
Conference_Location :
Austin, TX
DOI :
10.1109/GlobalSIP.2013.6737016
