Previous | [1] | [2] | [3] | [4] | [5] | [6] |

A New Distributed Maximum Flow Algorithm

for Planar Directed Network

**Jyh-Horng Chern and Shian-Shyong Tseng ^{+}**

National Chiao Tung University

Hsinchu, Taiwan 30050, Republic of China

National Chiao Tung University

Hsinchu, Taiwan 30050, Republic of China

In this paper we present a distributed algorithm for maximum flow in a planar network with source s and sink t both on the outer boundary face. The distributed algorithm is based on Berge's centralized uppermost path algorithm. In our distributed algorithm, both the message complexity and the time delay complexity are equal to *O*(*n*^{2}), where *n* is the number of nodes in the planar network.

Keywords: distributed algorithm, asynchronous communication network, maximum flow algorithm, uppermost path algorithm, message and time delay complexities

Received December 27, 1988; revised February 12, 1990.

Communicated by Chin-Chen Chang.