Abstract
Several optimalization algorithms have been proposed for the solution of the basic network flow algorithms, such as the minimal and the multiterminal minimal path of a network having cost (distance) function, maximal flow of a capacitated network.
In this paper we present these algorithms in a special network in which on the edges a gain function is given. On the edge (x,y) of the network a t(x,y) transportation cost is defined. In the course of the transportation on the edge (x,y) the goods loose a part of there weight. If one unit of goods is transported from point x to point y then k(x,y) unite of goods arrive at point y, where 0<k(x,y)<1. The above mentioned 3 algorithms are presented in the network having gains.
These problems are interested not only theoretically, but in the practice too. For example the maximal flow problem could be used in the case of electrical network, where we are interested to know the amount of electricity on the edges of the network.
This is a preview of subscription content, log in via an institution to check access.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Preview
Unable to display preview. Download preview PDF.
Similar content being viewed by others
References
Bakó, A.: On the Determination of the Shortest Path in a Network Having Gains. Operationsforschung und Statistik 4, 63–68 (1973)
Bellman, R.: On a Routing Problem. Quarterly of Appl. Math. 16, 87–90 (1958)
Charnes, A., Raike, W.M.: One-Pass Algorithms for Some Generalized Network Prblems. Operations Research 14, 914–923 (1966)
Cormen, T.H., Leiserson, E.C., Rivert, R.L.: Introduction to Algorithms, p. 1062. MIT Press, Cambridge (2001)
Dantzig, G.B.: All Shortest Routes in a Graph, Operations Research House, Stanford University, TR 66-3 (1966)
Dreyfus, S.: An Appraisal of Some Shortest Path Algorithms. Operations Research 17, 395–412 (1969)
Ford Jr., L.R., Fulkerson, D.R.: Flows in Networks. Princeton University Press, Princeton (1962)
Glover, F., Klingman, D., Napier, A.: A Note on Finding All Shortest Path, Management Science Report Series, Univ. of Colorado, Bulder, Colorado (1972)
Hu, T.C.: A Decomposition Algorithm for Shortest Path in a Network. Operations Research 16, 91–102 (1968)
Jarvis, J.J., Jezior, A.M.: Maximal Flow with Gains through a Special Network. Perations Researc. 19, 678–688 (1971)
Jewell, W.S.: Optimal Flow through Network with Gains. Operations Research 10, 476–499 (1962)
Warshall, S.: A Theorem on Boolean Matrices. J. of ACM 9, 11–12 (1962)
Yen, J.Y.: On Hu’s Decomposition Algorithm for Shortest Path in a Network. Operations Research 19, 983–985 (1971)
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2009 Springer-Verlag Berlin Heidelberg
About this chapter
Cite this chapter
Bakó, A., Földesi, P., Szűts, I. (2009). Determination the Basic Network Algorithms with Gains. In: Rudas, I.J., Fodor, J., Kacprzyk, J. (eds) Towards Intelligent Engineering and Information Technology. Studies in Computational Intelligence, vol 243. Springer, Berlin, Heidelberg. https://doi.org/10.1007/978-3-642-03737-5_32
Download citation
DOI: https://doi.org/10.1007/978-3-642-03737-5_32
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-642-03736-8
Online ISBN: 978-3-642-03737-5
eBook Packages: EngineeringEngineering (R0)