Title: Algebraic Characterizations of Flow-Network Typings
Author: Assaf Kfoury
Date: February 17, 2012
Abstract:
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.