nach oben

Erschienen in:

2018 | OriginalPaper | Buchkapitel

19. Multicommodity Flows and Edge-Disjoint Paths

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

The MULTICOMMODITY FLOW PROBLEM is a generalization of the MAXIMUM FLOW PROBLEM. Given a digraph with edge capacities, we now ask for an s-t-flow for several pairs (s, t) (we speak of several commodities), such that the total flow through any edge does not exceed the capacity. We specify the pairs (s, t) by a second digraph; for technical reasons we have an edge from t to s when we ask for an s-t-flow.

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 Bin-Packing

Nächstes Kapitel Network Design Problems

Frank, A. [1990]: Packing paths, circuits and cuts – a survey. In: Paths, Flows, and VLSI-Layout (B. Korte, L. Lovász, H.J. Prömel, A. Schrijver, eds.), Springer, Berlin 1990, pp. 47–100

Naves, G., and Sebő, A. [2009]: Multiflow feasibility: an annotated tableau. In: Research Trends in Combinatorial Optimization (W.J. Cook, L. Lovász, J. Vygen, eds.), Springer, Berlin 2009, pp. 261–283

Ripphausen-Lipa, H., Wagner, D., and Weihe, K. [1995]: Efficient algorithms for disjoint paths in planar graphs. In: Combinatorial Optimization; DIMACS Series in Discrete Mathematics and Theoretical Computer Science 20 (W. Cook, L. Lovász, P. Seymour, eds.), AMS, Providence 1995

Schrijver, A. [2003]: Combinatorial Optimization: Polyhedra and Efficiency. Springer, Berlin 2003, Chapters 70–76

Shmoys, D.B. [1996]: Cut problems and their application to divide-and-conquer. In: Approximation Algorithms for NP-Hard Problems (D.S. Hochbaum, ed.), PWS, Boston, 1996

Aumann, Y. and Rabani, Y. [1998]: An O(logk) approximate min-cut max-flow theorem and approximation algorithm. SIAM Journal on Computing 27 (1998), 291–301

Arora, S., Rao, S., and Vazirani, U. [2009]: Expander flows, geometric embeddings and graph partitioning. Journal of the ACM 56 (2009), Article 5

Arora, S., Hazan, E., and Kale, S. [2004]: \(O(\sqrt{\log n})\) approximation to SPARSEST CUT in \(\tilde{O}(n^{2})\) time. Proceedings of the 45th Annual IEEE Symposium on Foundations of Computer Science (2004), 238–247

Becker, M., and Mehlhorn, K. [1986]: Algorithms for routing in planar graphs. Acta Informatica 23 (1986), 163–176

Bienstock, D., and Iyengar, G. [2006]: Solving fractional packing problems in \(O^{{\ast}}(\frac{1} {\epsilon } )\) iterations. SIAM Journal on Computing 35 (2006), 825–854

Boesch, F., and Tindell, R. [1980]: Robbins’s theorem for mixed multigraphs. American Mathematical Monthly 87 (1980), 716–719

Charikar, M., Hajiaghayi, M.T., Karloff, H. and Rao, S. [2010]: ℓ ₂ ² spreading metrics for vertex ordering problems. Algorithmica 56 (2010), 577–604

Chekuri, C., and Khanna, S. [2007]: Edge-disjoint paths revisited. ACM Transactions on Algorithms 3 (2007), Article 46

Chudak, F.A., and Eleutério, V. [2005]: Improved approximation schemes for linear programming relaxations of combinatorial optimization problems. In: Integer Programming and Combinatorial Optimization; Proceedings of the 11th International IPCO Conference; LNCS 3509 (M. Jünger, V. Kaibel, eds.), Springer, Berlin 2005, pp. 81–96

Even, S., Itai, A., and Shamir, A. [1976]: On the complexity of timetable and multicommodity flow problems. SIAM Journal on Computing 5 (1976), 691–703

Feige, U., and Lee, J.R. [2007]: An improved approximation ratio for the minimum linear arrangement problem. Information Processing Letters 101 (2007), 26–29

Fleischer, L.K. [2000]: Approximating fractional multicommodity flow independent of the number of commodities. SIAM Journal on Discrete Mathematics 13 (2000), 505–520

Ford, L.R., and Fulkerson, D.R. [1958]: A suggested computation for maximal multicommodity network flows. Management Science 5 (1958), 97–101

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

Fortune, S., Hopcroft, J., and Wyllie, J. [1980]: The directed subgraph homeomorphism problem. Theoretical Computer Science 10 (1980), 111–121

Frank, A. [1980]: On the orientation of graphs. Journal of Combinatorial Theory B 28 (1980), 251–261

Frank, A. [1981]: How to make a digraph strongly connected. Combinatorica 1 (1981), 145–153

Frank, A. [1985]: Edge-disjoint paths in planar graphs. Journal of Combinatorial Theory B 39 (1985), 164–178

Frank, A., and Tardos, É. [1984]: Matroids from crossing families. In: Finite and Infinite Sets; Vol. I (A. Hajnal, L. Lovász, and V.T. Sós, eds.), North-Holland, Amsterdam, 1984, pp. 295–304

Garg, N., and Könemann, J. [2007]: Faster and simpler algorithms for multicommodity flow and other fractional packing problems. SIAM Journal on Computing 37 (2007), 630–652

Grigoriadis, M.D., and Khachiyan, L.G. [1996]: Coordination complexity of parallel price-directive decomposition. Mathematics of Operations Research 21 (1996), 321–340

Guruswami, V., Håstad, J., Manokaran, R., Raghavendra, P., and Charikar, M. [2011]: Beating the random ordering is hard: every ordering CSP is approximation resistant. SIAM Journal on Computing 40 (2011), 878–914

Hansen, M.D. [1989]: Approximation algorithms for geometric embeddings in the plane with applications to parallel processing problems. Proceedings of the 30th Annual IEEE Symposium on Foundations of Computer Science (1989), 604–609

Hirai, H. [2010]: Metric packing for K ₃ + K ₃. Combinatorica 30 (2010), 295–326

Hu, T.C. [1963]: Multi-commodity network flows. Operations Research 11 (1963), 344–360

Ibaraki, T., and Poljak, S. [1991]: Weak three-linking in Eulerian digraphs. SIAM Journal on Discrete Mathematics 4 (1991), 84–98

Karakostas, G. [2008]: Faster approximation schemes for fractional multicommodity flow problems. ACM Transactions on Algorithms 4 (2008), Article 13

Karp, R.M. [1972]: Reducibility among combinatorial problems. In: Complexity of Computer Computations (R.E. Miller, J.W. Thatcher, eds.), Plenum Press, New York 1972, pp. 85–103

Karzanov, A.V. [1987]: Half-integral five-terminus flows. Discrete Applied Mathematics 18 (1987) 263–278

Kawarabayashi, K., Kobayashi, Y., and Reed, B. [2012] The disjoint paths problem in quadratic time. Journal of Combinatorial Theory B 102 (2012), 424–435

Kawarabayashi, K., and Wollan, P. [2010]: A shorter proof of the graph minor algorithm: the unique linkage theorem. Proceedings of the 42th Annual ACM Symposium on Theory of Computing (2010), 687–694

Kleinberg, J. [1996]: Approximation algorithms for disjoint paths problems. PhD thesis, MIT, Cambridge 1996

Leighton, T., and Rao, S. [1999]: Multicommodity max-flow min-cut theorems and their use in designing approximation algorithms. Journal of the ACM 46 (1999), 787–832

Linial, N., London, E., and Rabinovich, Y. [1995]: The geometry of graphs and some of its algorithmic applications. Combinatorica 15 (1995), 215–245

Lomonosov, M. [1979]: Multiflow feasibility depending on cuts. Graph Theory Newsletter 9 (1979), 4

Lovász, L. [1976]: On two minimax theorems in graph. Journal of Combinatorial Theory B 21 (1976), 96–103

Lucchesi, C.L., and Younger, D.H. [1978]: A minimax relation for directed graphs. Journal of the London Mathematical Society II 17 (1978), 369–374

Matsumoto, K., Nishizeki, T., and Saito, N. [1986]: Planar multicommodity flows, maximum matchings and negative cycles. SIAM Journal on Computing 15 (1986), 495–510

Middendorf, M., and Pfeiffer, F. [1993]: On the complexity of the disjoint path problem. Combinatorica 13 (1993), 97–107

Müller, D., Radke, K., and Vygen, J. [2011]: Faster min-max resource sharing in theory and practice. Mathematical Programming Computation 3 (2011), 1–35

Nagamochi, H., and Ibaraki, T. [1989]: On max-flow min-cut and integral flow properties for multicommodity flows in directed networks. Information Processing Letters 31 (1989), 279–285

Nash-Williams, C.S.J.A. [1969]: Well-balanced orientations of finite graphs and unobtrusive odd-vertex-pairings. In: Recent Progress in Combinatorics (W. Tutte, ed.), Academic Press, New York 1969, pp. 133–149

Naves, G. [2009]: The hardness of routing two pairs on one face. Les cahiers Leibniz, Technical Report No. 177, Grenoble 2009

Nishizeki, T., Vygen, J., and Zhou, X. [2001]: The edge-disjoint paths problem is NP-complete for series-parallel graphs. Discrete Applied Mathematics 115 (2001), 177–186

Okamura, H., and Seymour, P.D. [1981]: Multicommodity flows in planar graphs. Journal of Combinatorial Theory B 31 (1981), 75–81

Räcke, H. [2008]: Optimal hierarchical decompositions for congestion minimization in networks. Proceedings of the 40th Annual ACM Symposium on Theory of Computing (2008), 255–264

Raghavan, P., and Thompson, C.D. [1987]: Randomized rounding: a technique for provably good algorithms and algorithmic proofs. Combinatorica 7 (1987), 365–374

Robertson, N., and Seymour, P.D. [1986]: Graph minors VI; Disjoint paths across a disc. Journal of Combinatorial Theory B 41 (1986), 115–138

Robertson, N., and Seymour, P.D. [1995]: Graph minors XIII; The disjoint paths problem. Journal of Combinatorial Theory B 63 (1995), 65–110

Rothschild, B., and Whinston, A. [1966]: Feasibility of two-commodity network flows. Operations Research 14 (1966), 1121–1129

Scheffler, P. [1994]: A practical linear time algorithm for disjoint paths in graphs with bounded tree-width. Technical Report No. 396/1994, FU Berlin, Fachbereich 3 Mathematik

Schwärzler, W. [2009]: On the complexity of the planar edge-disjoint paths problem with terminals on the outer boundary. Combinatorica 29 (2009), 121–126

Sebő, A. [1993]: Integer plane multiflows with a fixed number of demands. Journal of Combinatorial Theory B 59 (1993), 163–171

Seymour, P.D. [1980]: Four-terminus flows. Networks 10 (1980), 79–86

Seymour, P.D. [1981]: On odd cuts and multicommodity flows. Proceedings of the London Mathematical Society (3) 42 (1981), 178–192

Shahrokhi, F., and Matula, D.W. [1990]: The maximum concurrent flow problem. Journal of the ACM 37 (1990), 318–334

Sherman, J. [2009]: Breaking the multicommodity flow barrier for \(O(\sqrt{\log n})\)-approximations to sparsest cut. Proceedings of the 50th Annual IEEE Symposium on Foundations of Computer Science (2009), 363–372

Vygen, J. [1995]: NP-completeness of some edge-disjoint paths problems. Discrete Applied Mathematics 61 (1995), 83–90

Wagner, D., and Weihe, K. [1995]: A linear-time algorithm for edge-disjoint paths in planar graphs. Combinatorica 15 (1995), 135–150

Young, N. [1995]: Randomized rounding without solving the linear program. Proceedings of the 6th Annual ACM-SIAM Symposium on Discrete Algorithms (1995), 170–178

Titel: Multicommodity Flows and Edge-Disjoint Paths
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_19

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"