Some new models for multiprocessor interconnection networks
DOI:
https://doi.org/10.2298/YJOR160315020CKeywords:
spectra of graphs, tightness, interconnection networks, graph operationAbstract
A multiprocessor system can be modeled by a graph G. The vertices of G correspond to processors while edges represent links between processors. To find suitable models for multiprocessor interconnection networks (briefly MINs), one can apply tools and techniques of spectral graph theory. In this paper, we extend some of the existing results and present several graphs which could serve as models for efficient MINs based on the small values of the previously introduced graph tightness. These examples of possible MINs arise as a result of some well-known and widely used graph operations. We also examine the suitability of strongly regular graphs (briefly SRGs) to model MINs, and prove the uniqueness of some of them.References
Caporossi, G., Hansen, P., “Variable neighborhood search for extremal graphs: 1 The AutoGraphiX system”, Discrete Mathematics, 212(1-2)(2000) 29-44.
Cvetković, D., Davidović, T., “Applications of some graph invariants to the analysis of multiprocessor topologies”, YUJOR-Yugoslav Journal of Operations Research, 18 (2)(2008) 173-186.
Cvetković, D., Davidović, T., “Well-suited multiprocessor topologies with a small number of processors”, Novi Sad Journal of Mathematics, 38 (3)(2008) 209-217.
Cvetković, D., Davidović, T., “Multiprocessor interconnection networks with small tightness”, International Journal of Foundations of Computer Science, 20 (5)(2009) 941-963.
Cvetković, D., Davidović, T., Multiprocessor interconnection networks, Applications of Graph Spectra, Zbornik radova 13(21), eds. D. Cvetković, I. Gutman, Mathematical Institute SANU, Belgrade, 2009, 33-63. Second improved edition: Selected Topics on Applications of Graph Spectra, Zbornik radova 14 (22)(2011) 35-62.
Cvetković, D., Davidović, T., Ilić, A., Simić, S.K., “Graphs for small multiprocessor interconnection networks”, Applied Mathematics and Computation, 217(2010) 2468-2480.
Cvetković, D., Doob, M., Sachs, H., Spectra of Graphs, Theory and Application, 3rd edition, Johann Ambrosius Barth Verlag, Heidelberg-Leipzig, 1995.
Cvetković, D.M., Rowlinson, P., Simić, S., An Introduction to the Theory of Graph Spectra, Cambridge University Press, 2010.
Cvetković, D., Rowlinson, P., Simić, S., Spectral Generalizations of Line Graphs: On Graphs with Least Eigenvalue 2, Cambridge University Press, Cambridge, 2004.
Delorme, C., Tillich, J-P., “The spectrum of de Bruijn and Kautz graphs”, European Journal of Combinatorics 19 (3)(1998) 307-319.
Elsässer, R., Královič, R., Monien, B., “Sparse topologies with small spectrum size”, Theoretical Computer Science, 307(2003) 549-565.
Qiu, K. and Das, S.K., “Interconnection networks and their eigenvalues”, International Journal of Foundations of Computer Science, 14 (3) (2003) 371-389.
Riess, C., Strehl, V. and Wanka, R., “The spectral relation between the Cube-Connected Cycles and the Shuffle-Exchange network”, IEEE ARCS Workshops, (2012) 1-6.
Spielman, D. A., “Spectral Graph Theory and its Applications”, 48th Annual IEEE Symposium on Foundations of Computer Science, 2007, 29-38.
Strok, V.V., “Circulant matrices and the spectra of de Bruijn graphs”, Ukrainian Mathematical Journal, 44 (11) (1992) 1446-1454.
Van Dam, E.R., Haemers, W.H., “Which graphs are determined by its spectrum?”, Linear Algebra and Its Applications, 373 (2003) 241-272.
Downloads
Published
Issue
Section
License
Copyright (c) 2016 YUJOR
This work is licensed under a Creative Commons Attribution-NonCommercial-NoDerivatives 4.0 International License.
