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

Journal of Inforamtion Science and Engineering, Vol.6 No.3, pp.159-172 (September 1990)
A New Distributed Maximum Flow Algorithm
for Planar Directed Network

Jyh-Horng Chern and Shian-Shyong Tseng+
 Institute of Computer Science and Information Engineering
National Chiao Tung University
Hsinchu, Taiwan 30050, Republic of China
+Department of Computer and Information Science
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(n2), 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.