A typing theory for flow networks (part I)
MetadataShow full item record
CitationKfoury, Assaf. "A Typing Theory for Flow Networks (Part I)", Technical Report BUCS-TR-2012-021, Computer Science Department, Boston University, December 31, 2012. [Available from: http://hdl.handle.net/2144/11409]
A flow network N is a capacited finite directed graph, with multiple sources (or input arcs) and multiple sinks (or output arcs). A flow f in N is feasible if it satisfies the usual flow-conservation condition at every node and lower-bound/upper-bound capacity constraints at every arc. We develop an algebraic theory of feasible flows in such networks with several beneficial consequences. We define and prove the correctness of an algorithm to infer, from a given flow network N, an algebraic characterization T of all assignments f of values to the input and output arcs of N that can be extended to feasible flows g. We call such a characterization T a principal typing for N, as there are other typings which are only valid for N because they define subsets of all input-output assignments f that can be extended to feasible flows g. A typing for N turns out to define a bounded convex polyhedral set (or polytope) in the n-dimensional vector space over real numbers where n is the total number of input and output arcs in N. We then establish necessary and sufficient conditions for an arbitrary typing to be a principal typing for some flow network. Based on these necessary and sufficient conditions, we define operations on typings that preserve their principality (to be typings for flow networks), and examine the implications for a typing theory of flow networks. These also support a divide-and-conquer approach to the design and analysis of flow-network algorithms.