Abstracts
Abstract
Let G be a graph, and let e be an edge of G. The main result of this paper is that any instance of the maximum-flow problem on G having e as the “return” edge can be solved in linear time provided G does not have a K3,3 minorcontaining e. The primary tool in proving this result is a new graph decomposition. In particular, it is shown that if G is 3-connected and does not have a K3,3 minor containing e, then it can be decomposed into planar graphs, “almost” planar graphs, and copies of K5.
Keywords:
- Maximum flow,
- Planar graphs,
- K3,
- 3 minor
Download the article in PDF to read it.
Download