PL EN


Preferencje help
Widoczny [Schowaj] Abstrakt
Liczba wyników
2009 | 29 | 3 | 511-519
Tytuł artykułu

Minimum congestion spanning trees of grids and discrete toruses

Treść / Zawartość
Warianty tytułu
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.
Wydawca
Rocznik
Tom
29
Numer
3
Strony
511-519
Opis fizyczny
Daty
wydano
2009
otrzymano
2008-02-28
zaakceptowano
2008-09-30
Twórcy
  • 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
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).
Typ dokumentu
Bibliografia
Identyfikatory
Identyfikator YADDA
bwmeta1.element.bwnjournal-article-doi-10_7151_dmgt_1461
JavaScript jest wyłączony w Twojej przeglądarce internetowej. Włącz go, a następnie odśwież stronę, aby móc w pełni z niej korzystać.