Algebraic characterizations of flow-network typings
MetadataShow full item record
Citation (published version)Kfoury, Assaf. "Algebraic Characterizations of Flow-Network Typings", Technical Report BUCS-TR-2012-004, Computer Science Department, Boston University, February 17, 2012. [Available from: http://hdl.handle.net/2144/11392]
A flow network N is a capacited finite directed graph, with multiple input ports/arcs and multiple output ports/arcs. A flow f in N assigns a non-negative real number to every arc and is feasible if it satisfies flow conservation at every node and respects lower-bound/upper-bound capacities at every arc. We develop an algebraic theory of feasible flows in such networks with several beneficial consequences. We define algorithms to infer, from a given flow network N, an algebraic classification, which we call a typing for N, of all assignments f_0 of values to the input and output arcs of N that can be extended to a feasible flow f. We then establish necessary and sufficient conditions on an arbitrary typing T guaranteeing that T is a valid typing for some flow network N. Based on these necessary and sufficient conditions, we define operations on typings that preserve their validity (to be typings for flow networks), and examine the implications for a typing theory of flow networks.