Finding a Single Most Augmenting Arc in a Planar Network with Ill-Known Arc Capacities

Finding a Single Most Augmenting Arc in a Planar Network with Ill-Known Arc Capacities

Let G(N; A) be a simple, connected and directed network with node set N and arc set A . Associated with each arc (i, j)A, there is a weight uij>0 uij that is the capacity of the arc. Let s and t be two specified nodes in G(N; A) , the maximum continuous flow from the source node s to the sink node t which satisfies the capacity constraints is called the maximum flow of the network. An arc is called a single most augmenting arc in G(N; A) if the augmentation in its arc capacity results in the maximum increase of the maximum flow. In such an augmentation, the capacity augmented is assumed to be infinitely large. In this paper, we propose an algorithm for finding a single most augmenting arc in a planar network with fuzzy arc capacities.