Geodesic
Minimum congestion spanning trees of grids and discrete toruses
Discussiones Mathematicae. Graph Theory, Tome 29 (2009) no. 3, pp. 511-519.

Voir la notice de l'article provenant de la source Library of Science

The paper is devoted to estimates of the spanning tree congestion for grid graphs and discrete toruses of dimensions two and three.
Keywords: minimum congestion spanning tree, grid graph, discrete torus 
@article{DMGT_2009_29_3_a4,
     author = {Castej\'on, Alberto and Ostrovskii, Mikhail},
     title = {Minimum congestion spanning trees of grids and discrete toruses},
     journal = {Discussiones Mathematicae. Graph Theory},
     pages = {511--519},
     publisher = {mathdoc},
     volume = {29},
     number = {3},
     year = {2009},
     language = {en},
     url = {http://geodesic.mathdoc.fr/item/DMGT_2009_29_3_a4/}
}
TY  - JOUR
AU  - Castejón, Alberto
AU  - Ostrovskii, Mikhail
TI  - Minimum congestion spanning trees of grids and discrete toruses
JO  - Discussiones Mathematicae. Graph Theory
PY  - 2009
SP  - 511
EP  - 519
VL  - 29
IS  - 3
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/item/DMGT_2009_29_3_a4/
LA  - en
ID  - DMGT_2009_29_3_a4
ER  - 
%0 Journal Article
%A Castejón, Alberto
%A Ostrovskii, Mikhail
%T Minimum congestion spanning trees of grids and discrete toruses
%J Discussiones Mathematicae. Graph Theory
%D 2009
%P 511-519
%V 29
%N 3
%I mathdoc
%U http://geodesic.mathdoc.fr/item/DMGT_2009_29_3_a4/
%G en
%F DMGT_2009_29_3_a4
Castejón, Alberto; Ostrovskii, Mikhail. Minimum congestion spanning trees of grids and discrete toruses. Discussiones Mathematicae. Graph Theory, Tome 29 (2009) no. 3, pp. 511-519. http://geodesic.mathdoc.fr/item/DMGT_2009_29_3_a4/

[1] 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.

[2] B. Bollobás and I. Leader, Edge-isoperimetric inequalities in the grid, Combinatorica 11 (1991) 299-314, doi: 10.1007/BF01275667.

[3] J. Clark and D.A. Holton, A First Look at Graph Theory (World Scientific, River Edge, N.J., 1991).

[4] R. Cypher, Theoretical aspects of VLSI pin limitations, SIAM J. Comput. 22 (1993) 356-378, doi: 10.1137/0222027.

[5] F. Harary, Graph Theory (Addison-Wesley Publishing Company, 1969).

[6] C. Jordan, Sur les assemblages de lignes, J. Reine Angew. Math. 70 (1869) 185-190, doi: 10.1515/crll.1869.70.185.

[7] M.I. Ostrovskii, Minimal congestion trees, Discrete Math. 285 (2004) 219-226, doi: 10.1016/j.disc.2004.02.009.

[8] M.I. Ostrovskii, Sobolev spaces on graphs, Quaestiones Mathematicae 28 (2005) 501-523, doi: 10.2989/16073600509486144.

[9] M.I. Ostrovskii, Minimum congestion spanning trees in bipartite and random graphs, preprint, 2007.

[10] M. Snir, I/O limitations on multi-chip VLSI systems, in: 19th Allerton Conference on Communication, Control, and Computing, 1981, pp. 224-231.

[11] B.Y. Wu and K.-M. Chao, Spanning trees and optimization problems (Boca Raton, Chapman Hall/CRC, 2004).