Hostname: page-component-78c5997874-g7gxr Total loading time: 0 Render date: 2024-11-05T23:31:08.418Z Has data issue: false hasContentIssue false
  • English
  • Français

On Canonical Concurrent Flows, Crossing Number and Graph Expansion

Published online by Cambridge University Press:  12 September 2008

Farhad Shahrokhi  and
László A. Székely
Farhad Shahrokhi
Affiliation:
University of North Texas, Denton TX
László A. Székely
Affiliation:
Eötvös University, Budapest and University of New Mexico, Albuquerque NM
Get access Rights & Permissions [Opens in a new window]

Abstract

We define and efficiently compute the canonical flow on a graph, which is a certain feasible solution for the concurrent flow problem and exhibits invariance under the action of the automorphism group of the graph. Using estimates for the congestion of our canonical flow, we derive lower bounds on the crossing number, bisection width, and the edge and vertex expansion of a graph in terms of sizes of the edge and vertex orbits and the average distance in the graph. We further exhibit classes of graphs for which our lower bounds are tight within a multiplicative constant. Also, in cartesian product graphs a concurrent flow is constructed in terms of the concurrent flows in the factors, and in this way lower bounds for the edge and vertex expansion of the power graphs are derived in terms of that of the original graph.

Type
Research Article
Information
Combinatorics, Probability and Computing , Volume 3 , Issue 4 , December 1994 , pp. 523 - 543
Copyright
Copyright © Cambridge University Press 1994

Access options

Get access to the full version of this content by using one of the access options below. (Log in options will check for institutional or personal access. Content may require purchase if you do not have access.)

References

[1]Aldous, D. (1987) On the Markov chain simulation method for uniform combinatorial distribution and simulation annealing. Probability in Eng. and Inf. Sci. 1 33–46.CrossRefGoogle Scholar
[2]Babai, L. (1991) Local expansion of vertex transitive graphs and random generation in finite groups. Proc. 23rd ACM Symp. on Theory of Computing, New Orleans LA164–174.Google Scholar
[3]Babai, L. and Szegedy, M. (1992) Local expansion of symmetrical graphs. Combinatorics, Probability and Computing 1 1–11.CrossRefGoogle Scholar
[4]Bianchini, R. and Shen, J. P. (1987) Interprocessor traffic scheduling algorithms for multiple processor networks. IEEE Trans. Computers C-36 396–409.CrossRefGoogle Scholar
[5]Bollobás, B. (1986) Combinatorics, Cambridge University Press.Google Scholar
[6]Bollobás, B. and Leader, I. (1991) Compression and isoperimetric inequalities. J. Comb. Theory (A) 56 47–62.CrossRefGoogle Scholar
[7]Bollobás, B. and Leader, I. (1991) Edge-isoperimetric inequalities in the grid. Combinatorica 11 299–314.CrossRefGoogle Scholar
[8]Chartrand, G. and Lesniak, L. (1986) Graphs and Digraphs, Wadsworth and Books/Cole Mathematics Series.Google Scholar
[9]Chung, F., Coffman, E., Reiman, M. and Simon, B. (1987) The forwarding index of communication networks. IEEE Trans, on Information Theory 33 224–232.CrossRefGoogle Scholar
[10]Dyer, M., Frieze, A. and Kannan, R. (1989) A random polynomial time algorithm for approximating the volume of convex bodies. Proc. 21st ACM Symp. on Theory of Computing 289–292.Google Scholar
[11]Feige, U., Goldwasser, S., Lovász, L., Safra, S. and Szegedy, M. (1991) Approximating clique is almost NP-complete. Proc. 32nd IEEE Symp. on Found, of Computer Sci. 164–174.Google Scholar
[12]Fernandez de la Vega, W. and Marquez Gordones, L. (1992) The forwarding indices of random graphs. Random Structures and Algorithms 3 207–216.CrossRefGoogle Scholar
[13]Ford, L. R. and Fulkerson, D. R. (1962) Flows in Networks, Princeton University Press.Google Scholar
[14]Garey, M. R. and Johnson, D. S. (1978) Computers and Intractability: A Guide to the Theory of NP-Completeness, W. H. Freeman and Co.Google Scholar
[15]Garey, M. R. and Johnson, D. S. (1983) Crossing number is NP-complete. SIAM J. Algebraic and Discrete Methods 4 312–316.CrossRefGoogle Scholar
[16]Gerla, M. (1974) A cut saturation algorithm for topological design of packet switched networks. Proc. Natl. Telecomm. Conference 1074–1085.Google Scholar
[17]Grigordiadis, M. D. and Khachiyan, L. (1991) Fast Approximation Schemes for Convex Programs, with Many Blocks and Coupling Constraints, Report DCS-TR-273 Rutgers University (to appear in SIAM Journal on Optimization).Google Scholar
[18]Hart, S. (1976) A note on the edges of the n-cube. Disc. Math. 14 157–163.CrossRefGoogle Scholar
[19]Heydemann, M. C., Meyer, J. C. and Sotteau, D. (1989) On forwarding index of networks. Discrete Appl. Math 23 103–123.CrossRefGoogle Scholar
[20]Hu, T. C. (1963) Multi-commodity network flows. J. ORSA 11 344–360.Google Scholar
[21]Karmarkar, N. (1984) A new polynomial time algorithm for linear programming. Combinatorica 4 373–395.CrossRefGoogle Scholar
[22]Klein, P., Agrawal, A., Ravi, R. and Rao, S. (1990) Approximation through multicommodity flow. Proc. 31th IEEE Symp. on Foundations of Computer Science 726–737.Google Scholar
[23]Klein, P., Plotkin, S.A. and Rao, S. (1993) Planar graphs, multicommodity flows, and network decomposition. Proc. 25rd ACM Symp. on Theory of Computing.Google Scholar
[24]Klein, P., Ravi, R., Agrawal, A. and Rao, S. (submitted) An approximate max-flow min-cutrelation for multicommodity flow, with applications.Google Scholar
[25]Klein, P., Stein, C. and Tardos, E. (1990) Leighton-Rao might be practical: faster approximation algorithms for concurrent flow with uniform capacities. Proc. 22th ACM Symp. on Theory of Computing 310–321.Google Scholar
[26]Leader, I. (1991) Discrete isoperimetric inequalities. In: Bollobás, B. (ed.) Probabilistic combinatorics and its applications. Proc. of Symposia in Applied Mathematics 4457–80.CrossRefGoogle Scholar
[27]Leighton, F. T. (1983) Complexity Issues in VLSI, MIT Press.Google Scholar
[28]Leighton, T., Makedon, F., Plotkin, S., Stein, C., Tardos, E. and Tragoudas, S. (1991) Fast approximation algorithms for multicommodity flow problems. Proc. 23rd ACM Symp. on Theory of Computing 101–111.Google Scholar
[29]Leighton, T. and Rao, S. (1988) An approximate max-flow min-cut theorem for uniform multicommodity flow problems with applications to approximation algorithms. Proc. 29th IEEE Symp. on Foundations of Computer Science 422–431.CrossRefGoogle Scholar
[30]Madej, T. (1991) Bounds for the crossing number of N-cube. J. Graph Theory 15 81–98.CrossRefGoogle Scholar
[31]Matula, D. W. and Dolev, D. (1982) Path-regular Graphs. Tech. Report 82-CSE-3, Southern Methodist University.Google Scholar
[32]Matula, D. W. and Shahrokhi, F. (1990) Sparsest cuts and bottlenecks in graphs. Disc. Applied Math. 27 113–123.CrossRefGoogle Scholar
[33]Mohar, B. (1989) Isoperimetric numbers of graphs. J. Comb. Theory (B) 47 274–291.CrossRefGoogle Scholar
[34]Okamura, H., Seymour, P. D. (1981) Multicommodity flows in planar graphs. J. Comb. Theory (B) 31 75–81.CrossRefGoogle Scholar
[35]Raghavan, P. (1986) Probabilistic construction of deterministic algorithms: approximating packing integer programs. Proc. 27th IEEE Symp. on the Foundations of Computer Science 10–18.Google Scholar
[36]Raghavan, P. and Thompson, C. D. (1991) Multiterminal global routing. Algorithmica 6 73–82.CrossRefGoogle Scholar
[37]Saad, R. (1991) Complexity of Forwarding Index Problem, Université de Paris-Sud, Lab. de Recherche en Informatique, Rapport No. 648.Google Scholar
[38]Shahrokhi, F. (1989) Approximation algorithms for the maximum concurrent flow problem. ORSA Journal on Computing 2 (1) 62–69.CrossRefGoogle Scholar
[39]Shahrokhi, F. and Matula, D. W. (1990) The maximum concurrent flow problem. J. Assoc. Computing Machinery 2:37 318–334.CrossRefGoogle Scholar
[40]Shahrokhi, F., Sýkora, O., Székely, L. A. and Vrťo, I. (in preparation) Bounds for the crossing number of a graph on a compact 2-manifold.Google Scholar
[41]Shahrokhi, F. and Székely, L. A. (1990) A combinatorial approach to the integral multicommodity flow problem with applications to packet routing. Presented at 855th AMS Meeting, Manhattan, Kansas 1990. Abstracts of Papers Presented to the AMS 11 156.Google Scholar
[42]Shahrokhi, F. and Székely, L. A. (1991) An Algebraic Approach to the Uniform Concurrent Multicommodity Flow Problem: Theory and Applications, Technical Report CRPDC-91–4, Dept. Computer Science, Univ. of North Texas.Google Scholar
[43]Shahrokhi, F. and Székely, L. A. (1992) Effective lower bounds for crossing number, bisection width and balanced vertex separators in terms of symmetry. In: Balas, E., Cournejols, G. and Kannan, R. (eds.) Integer Programming and Combinatorial Optimization, Proceedings of a conference held at Carnegie Mellon University,May 25–27, 1992, by the Mathematical Programming Society, CMU Press 102–113.Google Scholar
[44]Shahrokhi, F. and Székely, L. A. (submitted) Formulae for the optimal congestion of the uniform concurrent multicommodity flow.Google Scholar
[45]Sinclair, A. and Jerrum, M. (1988) Conductance and rapid mixing property for Markov chains. Proc. 20th ACM Symp. on Theory of Computing 235–244.Google Scholar
[46]Sýkora, O. and Vrťo, I. (1992) On the crossing number of hypercubes and cube connected cycles. In: Schmidt, G. and Berghammer, R. (eds.) Proc. 17th Intl. Workshop on Graph Theoretic Concepts in Computer Science WG'91. Spinger-Verlag Lecture Notes in Computer Science 570214–218.CrossRefGoogle Scholar
[47]White, A. T. (1984) Graphs, Groups and Surfaces, North-Holland.Google Scholar
[48]White, A. T. and Beineke, L. W. (1978) Topological graph theory. In: Beineke, L. W. and Wilson, R. J. (eds.) Selected Topics in Graph Theory, Academic Press 15–50.Google Scholar