A compositional approach to network algorithms
MetadataShow full item record
Citation (published version)Kfoury, Assaf. "A Compositional Approach to Network Algorithms", Technical Report BUCS-TR-2013-015, Computer Science Department, Boston University, November 23, 2013. [Available from: http://hdl.handle.net/2144/11423]
We present elements of a typing theory for flow networks, where “types”, “typings”, and “type inference” are formulated in terms of familiar notions from polyhedral analysis and convex optimization. Based on this typing theory, we develop an alternative approach to the design and analysis of network algorithms, which we illustrate by applying it to the max-flow problem in multiple-source, multiple-sink, capacited directed planar graphs.