Acyclic Network Generation and Maximal Flow Algorithms for Single Commodity Flow (Maximum Flow, Referent Methods).
1985
Online
Hochschulschrift
Zugriff:
In this study efficient algorithms are developed for solving the classical maximum value flow problem for a single commodity in a directed network. The developed acyclic network generation algorithm, a referent method called the Outnetwork algorithm has a worst case computational complexity of O(n('2)). It generates an acyclic, auxiliary network from an original network G, and attempts to maximize the number of flow augmenting chains in each generated Outnetwork. Two maximal flow algorithms were developed. The 1st Maximal Flow algorithm and the Network Blocking Flow (NBF) algorithm are used in either the Outnetworks or Dinic networks to determine maximal flows. The first of these algorithms uses a new concept of preflows and backflows at nodes, and increases flow in both forward and backward passes through the network. It somewhat resembles the maximal flow algorithm of Karzanov. The worst case computational complexity of the algorithm is O(n('2)) for maximal flow. The second algorithm, the NBF algorithm, uses an unconventional concept of setting the flow initially to residual capacity on each arc of the Outnetwork. Thus, it creates an infeasible flow vector violating the flow conservation rule at nodes. The flow is reduced in one backward pass and one forward pass, and the network is then pruned. The process is repeated until the source node or the sink node is deleted from the Outnetwork. The worst case computational complexity of the NBF algorithm is O(n('2)). It is conjectured that a time bound of O(m) can be attained using efficient data structures. The limited testing in four network classes indicated that the Outnetwork/NBF algorithm combination for maximum value flow is superior in two of the network classes, and has about equal performance in the two others when compared to the Dinic/MKM algorithm combination. The number of networks constructed for maximum value flow when comparing the Outnetwork algorithm to the Dinic algorithm, and the CPU time required when comparing the NBF algorithm against the MKM algorithm were the criteria used in arriving at this conclusion. Further testing as well as determining of efficient implementations of the algorithms and data structures seems essential.
Titel: |
Acyclic Network Generation and Maximal Flow Algorithms for Single Commodity Flow (Maximum Flow, Referent Methods).
|
---|---|
Autor/in / Beteiligte Person: | Waissi, Gary Ray Robert |
Link: | |
Veröffentlichung: | 1985 |
Medientyp: | Hochschulschrift |
Sonstiges: |
|