A Fixed-Parameter Linear-Time Algorithm for Maximum Flow in Planar Flow Networks

Abstract

We pull together previously established graph-theoretical results to produce the algorithm in the paper's title. The glue are three easy elementary lemmas.

arXiv comment14 pages, 2 figures, 18 references

References in corpus (1)

• A Compositional Approach to Network Algorithms

Cited by in corpus (1)

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