A Fixed-Parameter Linear-Time Algorithm to Compute Principal Typings of Planar Flow Networks

07/18/2018

∙

by   Assaf Kfoury, et al.

∙

0

∙

share

We present an alternative and simpler method for computing principal typings of flow networks. When limited to planar flow networks, the method can be made to run in fixed-parameter linear-time -- where the parameter not to be exceeded is what is called the edge-outerplanarity of the networks' underlying graphs.