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

Michael Todorov Todinov

Abstract


The paper discuses a new fundamental result in the theory of flow networks referred to as the ‘dual network theorem forstatic flow networks’. The theorem states that the maximum throughput flow in any static network is equal to the sum ofthe capacities of the edges coming out of the source, minus the total excess flow at all excess nodes, plus the maximumthroughput flow in the dual network. For very few imbalanced nodes in a flow network, determining the throughput flowin the dual network is a task significantly easier than determining the throughput flow in the original network. This createsthe basis of a very efficient algorithm for maximising the throughput flow in a network, by maximising the throughputflow in its dual network.Consequently, a new algorithm for maximising the throughput flow in a network has been proposed. For networks withvery few imbalanced nodes, in the case where only the maximum throughput flow is of interest, the proposed algorithmwill outperform any classical method for determining the maximum throughput flow.In this paper we also raise awareness of a fundamental flaw in classical algorithms for maximising the throughput flow instatic networks with directed edges. Despite the years of intensive research on static flow networks, the classicalalgorithms leave undesirable directed loops of flow in the optimised networks. These directed flow loops are associatedwith wastage of energy and resources and increased levels of congestion in the optimised networks. Consequently, analgorithm is also proposed for discovering and removing directed loops of flow in networks.


Full Text: PDF DOI: 10.5430/air.v2n1p81

Refbacks

  • There are currently no refbacks.


Creative Commons License
This work is licensed under a Creative Commons Attribution 3.0 License.

Artificial Intelligence Research

ISSN 1927-6974 (Print)   ISSN 1927-6982 (Online)

Copyright © Sciedu Press 
To make sure that you can receive messages from us, please add the 'Sciedu.ca' domain to your e-mail 'safe list'. If you do not receive e-mail in your 'inbox', check your 'bulk mail' or 'junk mail' folders.