Brona Brejova, Tomas Vinar. Weihe's algorithm for maximum flow in planar graphs. Unpublished manuscript, University of Waterloo, December 1999.

Download preprint: 99weihe.ps, 632Kb

Download from publisher: not available

Related www page: 99weihe.zip

Bibliography entry: BibTeX

Abstract:

The maximum flow problem has been one of the most well-studied problems in algorithmic
graph theory over the last 50 years. It has many important applications in many
different areas. Also many modifications of the problem were studied. In this project
we are interested in a special case of planar graphs. The first \$O(nlog n)\$ algorithm
for general planar (directed) case was developed by Weihe in 1997. This algorithm is
of our particular interest.

The main goal of this project was to implement Weihe's algorithm. During the work on
the project we have found several errors in the article. We have summarized errors and
corrected them in the report. Also we have completely described algorithm for removing
clockwise cycles in planar network. As far as we know this is the first such complete
description.

As a side effect of our work we have developed new algorithm for removing useless
edges in general graphs working in \$O(mlog n)\$ time. As far as we know this is the
first solution of this problem. The question whether there exists more efficient
solution at least for planar graphs remains open.

Finally, we have developed relatively simple method for implementing back
transformation. Back transformation was not described in the original article at all.

Our implementation is available in the file 99weihe.zip.

Last update: 10/01/2006