Show simple item record

dc.contributor.authorKfoury, Assafen_US
dc.date2012-12-31en_US
dc.date.accessioned2015-06-24T19:48:51Z
dc.date.available2015-06-24T19:48:51Z
dc.date.issued2013-03-04en_US
dc.identifier.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]en_US
dc.identifier.urihttps://hdl.handle.net/2144/11409
dc.description.abstractA 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.en_US
dc.description.sponsorshipNational Science Foundation (CCF-0820138)en_US
dc.language.isoen_USen_US
dc.publisherComputer Science Department, Boston Universityen_US
dc.relation.ispartofseriesBUCS Technical Reports;BUCS-TR-2012-021en_US
dc.titleA typing theory for flow networks (part I)en_US
dc.typeTechnical Reporten_US


Files in this item

This item appears in the following Collection(s)

Show simple item record