Abstract
Graph is a powerful mathematical tool applied in many fields as transportation, communication, informatics, economy, … In ordinary graph the weights of edges and vertexes are considered independently where the length of a path is the sum of weights of the edges and the vertexes on this path. However, in many practical problems, weights at a vertex are not the same for all paths passing this vertex, but depend on coming and leaving edges. The paper develops a model of extended network that can be applied to modelling many practical problems more exactly and effectively. The main contribution of this paper is sink toward source algorithm finding maximal flows on extended mixed networks.
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
Similar content being viewed by others
References
Chien, T.Q.: The problem to find the maximum flow on the network. The research project on the Ministry level, B2005-16-34, Vietnam (2005)
Chien, T.Q.: Weighted source-sink alternative algorithm. Univ. Danang-Vietnam J. Sci. Technol. 3(26), 99–105 (2008)
Chien, T.Q., Tue, N.M., Viet, T.N.: Shortest path algorithm on extended graphs. In: Proceedings of the 6th National Conference on Fundamental and Applied Information Technology Research (FAIR), Vietnam, pp. 522–527 (2013)
Taylor, M.A.P. (ed.): Transportation and traffic theory in the 21st Century. Pergamon Press Amsterdam, The Netherlands (2002)
Johnson, E.L., Committee Chair, Nemhauser, G.L.: Shortest paths and multicommodity network flow (2003)
Ngoc, V.T., Quoc, C.T., Van, T.N.: Improving computing performance for algorithm finding maximal flows on extended mixed networks. J. Inf. Comput. Sci. 075–080, England, UK (2015)
Trevisan, L.: Generalizations of the maximum flow problem. Stanford University-CS261: Optimization (2011)
Madry, A.: Faster approximation schemes for fractional multicommodity flow problems via dynamic graph algorithms. Massachusetts Institute of Technology (2009)
Author information
Authors and Affiliations
Corresponding author
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2016 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Ngoc, V.T., Bao, H.H., Quoc, C.T., Le Manh, T., Khanh, V.H.T. (2016). Sink Toward Source Algorithm Finding Maximal Flows on Extended Mixed Networks. In: Nguyen, N.T., Trawiński, B., Fujita, H., Hong, TP. (eds) Intelligent Information and Database Systems. ACIIDS 2016. Lecture Notes in Computer Science(), vol 9622. Springer, Berlin, Heidelberg. https://doi.org/10.1007/978-3-662-49390-8_24
Download citation
DOI: https://doi.org/10.1007/978-3-662-49390-8_24
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-662-49389-2
Online ISBN: 978-3-662-49390-8
eBook Packages: Computer ScienceComputer Science (R0)