Minimum congestion spanning trees of grids and discrete toruses

ArticleOriginal scientific text

Title

Authors ¹, ²

Department of Applied Mathematics I, Higher Technical School of Telecommunications Engineering (ETSIT), Universidad de Vigo Lagoas-Marcosende, 36200 Vigo (Pontevedra), Spain
Department of Mathematics and Computer Science, St. John's University, 8000 Utopia Parkway, Queens, NY 11439, USA

The paper is devoted to estimates of the spanning tree congestion for grid graphs and discrete toruses of dimensions two and three.

minimum congestion spanning tree, grid graph, discrete torus

R. Ahlswede and S.L. Bezrukov, Edge isoperimetric theorems for integer point arrays, Appl. Math. Lett. 8 (1995) 75-80, doi: 10.1016/0893-9659(95)00015-I.
B. Bollobás and I. Leader, Edge-isoperimetric inequalities in the grid, Combinatorica 11 (1991) 299-314, doi: 10.1007/BF01275667.
J. Clark and D.A. Holton, A First Look at Graph Theory (World Scientific, River Edge, N.J., 1991).
R. Cypher, Theoretical aspects of VLSI pin limitations, SIAM J. Comput. 22 (1993) 356-378, doi: 10.1137/0222027.
F. Harary, Graph Theory (Addison-Wesley Publishing Company, 1969).
C. Jordan, Sur les assemblages de lignes, J. Reine Angew. Math. 70 (1869) 185-190, doi: 10.1515/crll.1869.70.185.
M.I. Ostrovskii, Minimal congestion trees, Discrete Math. 285 (2004) 219-226, doi: 10.1016/j.disc.2004.02.009.
M.I. Ostrovskii, Sobolev spaces on graphs, Quaestiones Mathematicae 28 (2005) 501-523, doi: 10.2989/16073600509486144.
M.I. Ostrovskii, Minimum congestion spanning trees in bipartite and random graphs, preprint, 2007.
M. Snir, I/O limitations on multi-chip VLSI systems, in: 19th Allerton Conference on Communication, Control, and Computing, 1981, pp. 224-231.
B.Y. Wu and K.-M. Chao, Spanning trees and optimization problems (Boca Raton, Chapman & Hall/CRC, 2004).