Minimum congestion spanning trees of grids and discrete toruses

• Autorzy: Alberto Castejón , Mikhail I. Ostrovskii
• Języki publikacji: EN

Abstrakty

EN

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

Słowa kluczowe

EN

minimum congestion spanning tree; grid graph; discrete torus

Kategorie tematyczne

• 05C05: Trees
• 05C35: Extremal problems

• Wydawca: De Gruyter Open
• Czasopismo: Discussiones Mathematicae Graph Theory
• Rocznik: 2009
• Tom: 29
• Numer: 3
• Strony: 511-519

Daty

wydano

2009

otrzymano

2008-02-28

zaakceptowano

2008-09-30

Twórcy

autor

Alberto Castejón

• Department of Applied Mathematics I, Higher Technical School of Telecommunications Engineering (ETSIT), Universidad de Vigo Lagoas-Marcosende, 36200 Vigo (Pontevedra), Spain

autor

Mikhail I. Ostrovskii

• Department of Mathematics and Computer Science, St. John's University, 8000 Utopia Parkway, Queens, NY 11439, USA

Bibliografia

• [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).

Identyfikatory

DOI

10.7151/dmgt.1461