The dual network theorem for static flow networks and its application for maximising the throughput flow

A large number of algorithms have been proposed for solving the maximum flow problem by using a graph representation of the flow network. Most of this research has been focused mainly on static flow networks, where no failure of components is considered. Research related to static flow networks has already been comprehensively reviewed [1-3, 11, 16].

A substantial part of this research has been focused on calculating the maximum flow transmitted from sources to sinks, for static flow networks. Various distinct approaches for solving this problem have been proposed.

The first big category of methods for maximising the throughput flow in networks includes methods which start from an empty network and gradually saturate the edges with flow, until the whole network is fully saturated with flow[4, 5, 7-10, 13, 15]. Within this big category, two major sub-categories of flow maximisation algorithms can be distinguished. The first sub-category includes path augmentation algorithms which, at all steps, preserve the feasibility of the network flow until the maximum flow is attained [4, 7, 8]. Thus, the Ford-Fulkerson algorithm [8] is based on finding available flow paths and augmenting them with flow until no more augmentable flow paths can be found. An improvement compared to the Ford-Fulkerson algorithm is the Edmonds and Karp algorithm [7], based on finding the shortest augmentable source-to- sink path.

The second sub-category of methods for maximising the flow in a network with empty edges, includes the preflow-push algorithms, which preserve the maximum flow, until a feasible flow is attained [9, 13, 15]. The preflow-push algorithms maintain a preflow, for which the capacity constraints on the edges is honoured but the flow conservation law at the nodes may be violated in the followings sense: each node other than the source may contain excess flow. In other words, the sum of the flows that go into the node may be greater than the sum of the flows leaving the node. The algorithm works to convert the preflow into a feasible flow. This is done by including labels on the nodes indicating their ‘height’ with respect to the source node. Flow is pushed from a node with a higher height to a node with a lower height. If this cannot be done for a particular node, a relabeling operation is included, which increases the height of the node. Continuing this process, until no internal node (other than the source and the sink) has an excess flow, guarantees that the maximum throughput flow has been reached [14].

Most of the algorithms for maximizing the flow in static flow networks have polynomial time complexity. The running time of the algorithms for maximizing the flow in static networks however, can often be improved significantly, if the particular network topology is exploited directly. For planar networks for example, very efficient throughput flow maximisation algorithms have been designed [12]. For networks with tree topology, a very efficient algorithm for maximising the throughput flow can be designed, with linear worst-case running time, in the number of edges in the network (Todinov [21]). These algorithms take advantage of the planar topology and tree topology and their running time is superior to the running time of algorithms handling networks with arbitrary topology.

Recently, a principally different approach for maximising the flow in static flow networks was proposed by Dong et al. [6], based on the concept of starting from a fully saturated with flow network. The draining algorithm proposed in Dong et al.[6] starts from a network with fully saturated edges, which also includes a backward edge connecting the sink with the source. The algorithm drains flow from paths connecting deficit nodes and excess nodes, until all nodes become balanced and a maximum throughput flow is attained. In effect, the draining algorithm conducts balancing of excess and deficit nodes until the excess and deficit flow at the nodes disappears. The node balancing is conducted along the shortest augmentable paths between excess and deficit nodes.

For full text: click here

(Author: Michael Todorov Todinov

Published by Sciedu Press)