# Minimum congestion spanning trees of grids and discrete toruses

Alberto Castejón; Mikhail I. Ostrovskii

Discussiones Mathematicae Graph Theory (2009)

- Volume: 29, Issue: 3, page 511-519
- ISSN: 2083-5892

## Access Full Article

top## Abstract

top## How to cite

topAlberto Castejón, and Mikhail I. Ostrovskii. "Minimum congestion spanning trees of grids and discrete toruses." Discussiones Mathematicae Graph Theory 29.3 (2009): 511-519. <http://eudml.org/doc/271028>.

@article{AlbertoCastejón2009,

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

author = {Alberto Castejón, Mikhail I. Ostrovskii},

journal = {Discussiones Mathematicae Graph Theory},

keywords = {minimum congestion spanning tree; grid graph; discrete torus},

language = {eng},

number = {3},

pages = {511-519},

title = {Minimum congestion spanning trees of grids and discrete toruses},

url = {http://eudml.org/doc/271028},

volume = {29},

year = {2009},

}

TY - JOUR

AU - Alberto Castejón

AU - Mikhail I. Ostrovskii

TI - Minimum congestion spanning trees of grids and discrete toruses

JO - Discussiones Mathematicae Graph Theory

PY - 2009

VL - 29

IS - 3

SP - 511

EP - 519

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

LA - eng

KW - minimum congestion spanning tree; grid graph; discrete torus

UR - http://eudml.org/doc/271028

ER -

## References

top- [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. Zbl0830.05040
- [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). Zbl0765.05001
- [4] R. Cypher, Theoretical aspects of VLSI pin limitations, SIAM J. Comput. 22 (1993) 356-378, doi: 10.1137/0222027. Zbl0770.68080
- [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. Zbl1092.05035
- [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). Zbl1072.90047

## Citations in EuDML Documents

top## NotesEmbed ?

topTo embed these notes on your page include the following JavaScript code on your page where you want the notes to appear.