nach oben

Erschienen in:

2018 | OriginalPaper | Buchkapitel

8. Network Flows

verfasst von : Bernhard Korte, Jens Vygen

Erschienen in: Combinatorial Optimization

Verlag: Springer Berlin Heidelberg

Einloggen

Aktivieren Sie unsere intelligente Suche, um passende Fachinhalte oder Patente zu finden.

search-config

KI-gestützte Suche

Aus

Abstract

In this and the next chapter we consider flows in networks. We have a digraph G with edge capacities \(u: E(G) \rightarrow \mathbb{R}_{+}\) and two specified vertices s (the source) and t (the sink). The quadruple (G, u, s, t) is sometimes called a network .

Sie haben noch keine Lizenz? Dann Informieren Sie sich jetzt über unsere Produkte:

Springer Professional "Wirtschaft+Technik"

Online-Abonnement

Mit Springer Professional "Wirtschaft+Technik" erhalten Sie Zugriff auf:

über 102.000 Bücher
über 537 Zeitschriften

aus folgenden Fachgebieten:

Automobil + Motoren
Bauwesen + Immobilien
Business IT + Informatik
Elektrotechnik + Elektronik
Energie + Nachhaltigkeit
Finance + Banking
Management + Führung
Marketing + Vertrieb
Maschinenbau + Werkstoffe
Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

Jetzt informieren

Springer Professional "Technik"

Online-Abonnement

Mit Springer Professional "Technik" erhalten Sie Zugriff auf:

über 67.000 Bücher
über 390 Zeitschriften

aus folgenden Fachgebieten:

Automobil + Motoren
Bauwesen + Immobilien
Business IT + Informatik
Elektrotechnik + Elektronik
Energie + Nachhaltigkeit
Maschinenbau + Werkstoffe

Jetzt Wissensvorsprung sichern!

Jetzt informieren

Springer Professional "Wirtschaft"

Online-Abonnement

Mit Springer Professional "Wirtschaft" erhalten Sie Zugriff auf:

über 67.000 Bücher
über 340 Zeitschriften

aus folgenden Fachgebieten:

Bauwesen + Immobilien
Business IT + Informatik
Finance + Banking
Management + Führung
Marketing + Vertrieb
Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

Jetzt informieren

Vorheriges Kapitel Shortest Paths

Nächstes Kapitel Minimum Cost Flows

Ahuja, R.K., Magnanti, T.L., and Orlin, J.B. [1993]: Network Flows. Prentice-Hall, Englewood Cliffs 1993

Cook, W.J., Cunningham, W.H., Pulleyblank, W.R., and Schrijver, A. [1998]: Combinatorial Optimization. Wiley, New York 1998, Chapter 3

Cormen, T.H., Leiserson, C.E., Rivest, R.L., and Stein, C. [2009]: Introduction to Algorithms. Third Edition. MIT Press, Cambridge 2009, Chapter 26

Ford, L.R., and Fulkerson, D.R. [1962]: Flows in Networks. Princeton University Press, Princeton 1962

Frank, A. [1995]: Connectivity and network flows. In: Handbook of Combinatorics; Vol. 1 (R.L. Graham, M. Grötschel, L. Lovász, eds.), Elsevier, Amsterdam, 1995

Frank, A. [2011]: Connections in Combinatorial Optimization. Oxford University Press, Oxford 2011

Goldberg, A.V., Tardos, É., and Tarjan, R.E. [1990]: Network flow algorithms. In: Paths, Flows, and VLSI-Layout (B. Korte, L. Lovász, H.J. Prömel, A. Schrijver, eds.), Springer, Berlin 1990, pp. 101–164

Gondran, M., and Minoux, M. [1984]: Graphs and Algorithms. Wiley, Chichester 1984, Chapter 5

Jungnickel, D. [2013]: Graphs, Networks and Algorithms. Fourth Edition. Springer, Berlin 2013

Phillips, D.T., and Garcia-Diaz, A. [1981]: Fundamentals of Network Analysis. Prentice-Hall, Englewood Cliffs 1981

Ruhe, G. [1991]: Algorithmic Aspects of Flows in Networks. Kluwer Academic Publishers, Dordrecht 1991

Schrijver, A. [2003]: Combinatorial Optimization: Polyhedra and Efficiency. Springer, Berlin 2003, Chapters 9,10,13–15

Tarjan, R.E. [1983]: Data Structures and Network Algorithms. SIAM, Philadelphia 1983, Chapter 8

Thulasiraman, K., and Swamy, M.N.S. [1992]: Graphs: Theory and Algorithms. Wiley, New York 1992, Chapter 12

Ahuja, R.K., Orlin, J.B., and Tarjan, R.E. [1989]: Improved time bounds for the maximum flow problem. SIAM Journal on Computing 18 (1989), 939–954

Borradaile, G. and Klein, P. [2009]: An O(nlogn) algorithm for maximum st-flow in a directed planar graph. Journal of the ACM 56 (2009), Article 9

Cheriyan, J., and Maheshwari, S.N. [1989]: Analysis of preflow push algorithms for maximum network flow. SIAM Journal on Computing 18 (1989), 1057–1086

Cheriyan, J., and Mehlhorn, K. [1999]: An analysis of the highest-level selection rule in the preflow-push max-flow algorithm. Information Processing Letters 69 (1999), 239–242

Cherkassky, B.V. [1977]: Algorithm of construction of maximal flow in networks with complexity of \(O(V ^{2}\sqrt{E})\) operations. Mathematical Methods of Solution of Economical Problems 7 (1977), 112–125 [in Russian]

Cheung, K.K.H., Cunningham, W.H., and Tang, L. [2006]: Optimal 3-terminal cuts and linear programming. Mathematical Programming 106 (2006), 1–23

Cheung, H.Y., Lau, L.C., and Leung, K.M. [2011]: Graph connectivities, network coding, and expander graphs. Proceedings of the 52nd Annual IEEE Symposium on Foundations of Computer Science (2011), 197–206

Dahlhaus, E., Johnson, D.S., Papadimitriou, C.H., Seymour, P.D., and Yannakakis, M. [1994]: The complexity of multiterminal cuts. SIAM Journal on Computing 23 (1994), 864–894

Dantzig, G.B., and Fulkerson, D.R. [1956]: On the max-flow min-cut theorem of networks. In: Linear Inequalities and Related Systems (H.W. Kuhn, A.W. Tucker, eds.), Princeton University Press, Princeton 1956, pp. 215–221

Dinic, E.A. [1970]: Algorithm for solution of a problem of maximum flow in a network with power estimation. Soviet Mathematics Doklady 11 (1970), 1277–1280

Dinitz, E.A., Karzanov, A.V., and Lomonosov, M.V. [1976]: On the structure of the system of minimum edge cuts of a graph. Issledovaniya po Diskretnoĭ Optimizatsii (A.A. Fridman, ed.), Nauka, Moscow, 1976, pp. 290–306 [in Russian]

Edmonds, J., and Karp, R.M. [1972]: Theoretical improvements in algorithmic efficiency for network flow problems. Journal of the ACM 19 (1972), 248–264

Elias, P., Feinstein, A., and Shannon, C.E. [1956]: Note on maximum flow through a network. IRE Transactions on Information Theory, IT-2 (1956), 117–119

Even, S., and Tarjan, R.E. [1975]: Network flow and testing graph connectivity. SIAM Journal on Computing 4 (1975), 507–518

Ford, L.R., and Fulkerson, D.R. [1956]: Maximal Flow Through a Network. Canadian Journal of Mathematics 8 (1956), 399–404

Ford, L.R., and Fulkerson, D.R. [1957]: A simple algorithm for finding maximal network flows and an application to the Hitchcock problem. Canadian Journal of Mathematics 9 (1957), 210–218

Frank, A. [1994]: On the edge-connectivity algorithm of Nagamochi and Ibaraki. Laboratoire Artemis, IMAG, Université J. Fourier, Grenoble, 1994

Fujishige, S. [2003]: A maximum flow algorithm using MA ordering. Operations Research Letters 31 (2003), 176–178

Gabow, H.N. [1995]: A matroid approach to finding edge connectivity and packing arborescences. Journal of Computer and System Sciences 50 (1995), 259–273

Gabow, H.N. [2006]: Using expander graphs to find vertex-connectivity. Journal of the ACM 53 (2006), 800–844

Galil, Z. [1980]: An \(O(V ^{\frac{5} {3} }E^{\frac{2} {3} })\) algorithm for the maximal flow problem. Acta Informatica 14 (1980), 221–242

Galil, Z., and Namaad, A. [1980]: An O(EV log² V ) algorithm for the maximal flow problem. Journal of Computer and System Sciences 21 (1980), 203–217

Gallai, T. [1958]: Maximum-minimum Sätze über Graphen. Acta Mathematica Academiae Scientiarum Hungaricae 9 (1958), 395–434

Goldberg, A.V., and Rao, S. [1998]: Beyond the flow decomposition barrier. Journal of the ACM 45 (1998), 783–797

Goldberg, A.V., and Tarjan, R.E. [1988]: A new approach to the maximum flow problem. Journal of the ACM 35 (1988), 921–940

Gomory, R.E., and Hu, T.C. [1961]: Multi-terminal network flows. Journal of SIAM 9 (1961), 551–570

Gusfield, D. [1990]: Very simple methods for all pairs network flow analysis. SIAM Journal on Computing 19 (1990), 143–155

Hao, J., and Orlin, J.B. [1994]: A faster algorithm for finding the minimum cut in a directed graph. Journal of Algorithms 17 (1994), 409–423

Henzinger, M.R., Rao, S., and Wang, D. [2017]: Local flow partitioning for faster edge connectivity. Proceedings of the 28th Annual ACM-SIAM Symposium on Discrete Algorithms (2017), 1919–1938

Henzinger, M.R., Rao, S., and Gabow, H.N. [2000]: Computing vertex connectivity: new bounds from old techniques. Journal of Algorithms 34 (2000), 222–250

Hoffman, A.J. [1960]: Some recent applications of the theory of linear inequalities to extremal combinatorial analysis. In: Combinatorial Analysis (R.E. Bellman, M. Hall, eds.), AMS, Providence 1960, pp. 113–128

Hu, T.C. [1969]: Integer Programming and Network Flows. Addison-Wesley, Reading 1969

Jelinek, F., and Mayeda, W. [1963]: On the maximum number of different entries in the terminal capacity matrix of oriented communication nets. IEEE Transactions on Circuit Theory 10 (1963), 307–308

Kamidoi, Y., Yoshida, N., and Nagamochi, H. [2007]: A deterministic algorithm for finding all minimum k-way cuts. SIAM Journal on Computing 36 (2007), 1329–1341

Karger, D.R. [2000]: Minimum cuts in near-linear time. Journal of the ACM 47 (2000), 46–76

Karger, D.R., and Levine, M.S. [1998]: Finding maximum flows in undirected graphs seems easier than bipartite matching. Proceedings of the 30th Annual ACM Symposium on Theory of Computing (1998), 69–78

Karger, D.R., and Stein, C. [1996]: A new approach to the minimum cut problem. Journal of the ACM 43 (1996), 601–640

Karzanov, A.V. [1973]: On finding a maximum flow in a network with special structure and some applications. In: Matematicheskie Voprosy Upravleniya Proizvodstvom 5 (L.A. Lyusternik, ed.), Moscow State University Press, Moscow, 1973, pp. 81–94 [in Russian]

Karzanov, A.V. [1974]: Determining a maximal flow in a network by the method of preflows. Soviet Mathematics Doklady 15 (1974), 434–437

Lee, Y.T., and Sidford, A. [2014]: Path finding methods for linear programming. Proceedings of the 55th Annual IEEE Symposium on Foundations of Computer Science (2014), 424–433

Mader, W. [1972]: Über minimal n-fach zusammenhängende, unendliche Graphen und ein Extremalproblem. Arch. Math. 23 (1972), 553–560

Mader, W. [1981]: On a property of n edge-connected digraphs. Combinatorica 1 (1981), 385–386

Malhotra, V.M., Kumar, M.P., and Maheshwari, S.N. [1978]: An O( | V |³) algorithm for finding maximum flows in networks. Information Processing Letters 7 (1978), 277–278

Menger, K. [1927]: Zur allgemeinen Kurventheorie. Fundamenta Mathematicae 10 (1927), 96–115

Nagamochi, H., and Ibaraki, T. [1992]: Computing edge-connectivity in multigraphs and capacitated graphs. SIAM Journal on Discrete Mathematics 5 (1992), 54–66

Nagamochi, H., and Ibaraki, T. [2000]: A fast algorithm for computing minimum 3-way and 4-way cuts. Mathematical Programming 88 (2000), 507–520

Nagamochi, H., Nishimura, K., and Ibaraki, T. [1997]: Computing all small cuts in an undirected network. SIAM Journal on Discrete Mathematics 10 (1997), 469–481

Orlin, J.B. [2013]: Max flows in O(nm) time, or better. Proceedings of the 45th Annual ACM Symposium on Theory of Computing (2013), 765–774

Phillips, S., and Dessouky, M.I. [1977]: Solving the project time/cost tradeoff problem using the minimal cut concept. Management Science 24 (1977), 393–400

Picard, J., and Queyranne, M. [1980]: On the structure of all minimum cuts in a network and applications. Mathematical Programming Study 13 (1980), 8–16

Queyranne, M. [1998]: Minimizing symmetric submodular functions. Mathematical Programming B 82 (1998), 3–12

Rose, D.J. [1970]: Triangulated graphs and the elimination process. Journal of Mathematical Analysis and Applications 32 (1970), 597–609

Shiloach, Y. [1978]: An O(nIlog² I) maximum-flow algorithm. Technical Report STAN-CS-78-802, Computer Science Department, Stanford University, 1978

Shiloach, Y. [1979]: Edge-disjoint branching in directed multigraphs. Information Processing Letters 8 (1979), 24–27

Shioura, A. [2004]: The MA ordering max-flow algorithm is not strongly polynomial for directed networks. Operations Research Letters 32 (2004), 31–35

Sleator, D.D. [1980]: An O(nmlogn) algorithm for maximum network flow. Technical Report STAN-CS-80-831, Computer Science Department, Stanford University, 1978

Sleator, D.D., and Tarjan, R.E. [1983]: A data structure for dynamic trees. Journal of Computer and System Sciences 26 (1983), 362–391

Su, X.Y. [1997]: Some generalizations of Menger’s theorem concerning arc-connected digraphs. Discrete Mathematics 175 (1997), 293–296

Stoer, M., and Wagner, F. [1997]: A simple min cut algorithm. Journal of the ACM 44 (1997), 585–591

Tarjan, R.E. [1972]: Depth first search and linear graph algorithms. SIAM Journal on Computing 1 (1972), 146–160

Thorup, M. [2008]: Minimum k-way cuts via deterministic greedy tree packing. Proceedings of the 40th Annual ACM Symposium on Theory of Computing (2008), 159–165

Tunçel, L. [1994]: On the complexity preflow-push algorithms for maximum flow problems. Algorithmica 11 (1994), 353–359

Vazirani, V.V., and Yannakakis, M. [1992]: Suboptimal cuts: their enumeration, weight, and number. In: Automata, Languages and Programming; Proceedings of the 19th ICALP conference; LNCS 623 (W. Kuich, ed.), Springer, Berlin 1992, pp. 366–377

Vygen, J. [2002]: On dual minimum cost flow algorithms. Mathematical Methods of Operations Research 56 (2002), 101–126

Weihe, K. [1997]: Maximum (s, t)-flows in planar networks in O( | V | log | V | ) time. Journal of Computer and System Sciences 55 (1997), 454–475

Whitney, H. [1932]: Congruent graphs and the connectivity of graphs. American Journal of Mathematics 54 (1932), 150–168

Titel: Network Flows
verfasst von: Bernhard Korte
Jens Vygen
Verlag: Springer Berlin Heidelberg
Buch: Combinatorial Optimization
Print ISBN: 978-3-662-56038-9

Electronic ISBN: 978-3-662-56039-6

Copyright-Jahr: 2018
DOI: https://doi.org/10.1007/978-3-662-56039-6_8

Springer Professional

Abstract

Bitte loggen Sie sich ein, um Zugang zu Ihrer Lizenz zu erhalten.

Sie haben noch keine Lizenz? Dann Informieren Sie sich jetzt über unsere Produkte:

Springer Professional "Wirtschaft+Technik"

Springer Professional "Technik"

Springer Professional "Wirtschaft"