A Fixed-Parameter Linear-Time Algorithm to Compute Principal Typings of Planar Flow Networks. (arXiv:1807.07067v1 [cs.DS])

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.

from cs updates on arXiv.org https://ift.tt/2NqIzWz
//