Minimum congestion spanning trees of grids and discrete toruses
Alberto Castejón ; Mikhail I. Ostrovskii
Discussiones Mathematicae Graph Theory, Tome 29 (2009), p. 511-519 / Harvested from The Polish Digital Mathematics Library
Access to full text
Full (PDF)

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

Publié le : 2009-01-01
EUDML-ID : urn:eudml:doc:271028 
@article{bwmeta1.element.bwnjournal-article-doi-10_7151_dmgt_1461,
     author = {Alberto Castej\'on and Mikhail I. Ostrovskii},
     title = {Minimum congestion spanning trees of grids and discrete toruses},
     journal = {Discussiones Mathematicae Graph Theory},
     volume = {29},
     year = {2009},
     pages = {511-519},
     zbl = {1193.05058},
     language = {en},
     url = {http://dml.mathdoc.fr/item/bwmeta1.element.bwnjournal-article-doi-10_7151_dmgt_1461}
}

Alberto Castejón; Mikhail I. Ostrovskii. Minimum congestion spanning trees of grids and discrete toruses. Discussiones Mathematicae Graph Theory, Tome 29 (2009) pp. 511-519. http://gdmltest.u-ga.fr/item/bwmeta1.element.bwnjournal-article-doi-10_7151_dmgt_1461/

[000] [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. | Zbl 0830.05040

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

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

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

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

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

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

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

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

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

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